cpp/recursion/basen_combos Source

Viewing cpp/recursion/basen_combos by redekopp@usc.edu. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

Complete the following program to print out all possible combinations
of a given base and number of digits. E.g. <tt>./bincombos</tt> with input <tt>4 2</tt>
should print out
<pre>
00
01
02
03
10
11
12
13
20
21
22
23
30
31
32
33
</pre>
With input <tt>2 3</tt> it should print out
<pre>
000
001
010
011
100
101
110
111
</pre>
With input <tt>10 1</tt> it should print out
<pre>
0
1
2
3
4
5
6
7
8
9
</pre>
To do this,
fill out the recursive function
<tt>basen_combos(int base, char arr[], int current, int len)</tt>.
It should try setting <tt>current</tt> to each possible value,
in turn and using recursion to go through all the options of the remaining digits.
<p>
Use the base case to check that a particular combination is ready for printing.
<p>
Use the recursive case to set the current digit place and recurse to the next
digit.

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

Originally by Mark Redekopp (redekopp@usc.edu) and Dave Pritchard (daveagp@gmail.com)

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

#include <iostream>
using namespace std;

void basen_combos(int base, char* array, int current, int len) {
// Code for base case (i.e. end of array)
// When do we know there are no more digits to show
// and what should we do if that is the case
\[
if(current == len){
array[len] = '\0';
cout << array << endl;
}
]\
// Code for recursive case
// If we're not at the last digit, then set that
// digit location to each of its possible values and
// each time you change the value use recursion to
// generate all the combinations of digits after it
//
// Remember to make the char version of digit x, use '0'+x
\[
else {
for(int i=0; i < base; i++){
array[current] = static_cast<char>(i) + '0';
basen_combos(base, array, current+1, len);
}
}
]\
}

int main() {
// read target, n, then n sorted inputs
int base, numDigits;
cin >> base >> numDigits;

// allocate an array to hold the current combo + null char
char* arr = new char[numDigits+1];

// Call the function to generate all binary combos
basen_combos(base, arr, 0, numDigits);

delete [] arr;
return 0;
}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

[
{"stdin": "2 3"},
{"stdin": "4 2"},
{"stdin": "10 1"},
{"stdin": "8 2"}
]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	Complete the following program to print out all possible combinations of a given base and number of digits. E.g. <tt>./bincombos</tt> with input <tt>4 2</tt> should print out <pre> 00 01 02 03 10 11 12 13 20 21 22 23 30 31 32 33 </pre> With input <tt>2 3</tt> it should print out <pre> 000 001 010 011 100 101 110 111 </pre> With input <tt>10 1</tt> it should print out <pre> 0 1 2 3 4 5 6 7 8 9 </pre> To do this, fill out the recursive function <tt>basen_combos(int base, char arr[], int current, int len)</tt>. It should try setting <tt>current</tt> to each possible value, in turn and using recursion to go through all the options of the remaining digits. <p> Use the base case to check that a particular combination is ready for printing. <p> Use the recursive case to set the current digit place and recurse to the next digit.
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	Originally by Mark Redekopp (redekopp@usc.edu) and Dave Pritchard (daveagp@gmail.com) remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <iostream> using namespace std; void basen_combos(int base, char* array, int current, int len) { // Code for base case (i.e. end of array) // When do we know there are no more digits to show // and what should we do if that is the case \[ if(current == len){ array[len] = '\0'; cout << array << endl; } ]\ // Code for recursive case // If we're not at the last digit, then set that // digit location to each of its possible values and // each time you change the value use recursion to // generate all the combinations of digits after it // // Remember to make the char version of digit x, use '0'+x \[ else { for(int i=0; i < base; i++){ array[current] = static_cast<char>(i) + '0'; basen_combos(base, array, current+1, len); } } ]\ } int main() { // read target, n, then n sorted inputs int base, numDigits; cin >> base >> numDigits; // allocate an array to hold the current combo + null char char* arr = new char[numDigits+1]; // Call the function to generate all binary combos basen_combos(base, arr, 0, numDigits); delete [] arr; return 0; }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`	[ {"stdin": "2 3"}, {"stdin": "4 2"}, {"stdin": "10 1"}, {"stdin": "8 2"} ]
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.