public class PrintStrLenK {
public static void main(String[] args){
int k = 2;
char[] set = {'0', '1'};
char[] str = new char[k];
generate(k, set, str, 0);
}
static void generate(int k, char[] set, char[] str, int index){
if (index == k){
System.out.println(new String(str));
}
else {
for (int i = 0; i < set.length; i++){
str[index] = set[i];
generate(k, set, str, index + 1);
}
}
}
}
I found this code, the problem is that I was asked to have just one char change between permutations
Output:
00
01
02
03
10 --> 2 Char changes. Not OK.
11
12
13
20 --> 2 Char changes. Not OK.
21
22
23
30 --> 2 Char changes. Not OK.
31
32
33
Should Be
00
01
02
03
13 --> 1 Char change. OK
12
11
10
20 -- > 1 Char change. OK
21
22
23
33 -- > 1 Char change. OK
32
31
30
It has to works with different sets and k. For Example
set = {'0', '1'} and k= 3.
000 001 011 010 110 111 101 100
set = {'0', '1','2','3'} and k= 3.
000 001 002 003 013 012 011 010 020 021 022 023 033 032 031 030 130 131 132 133 123 122 121 120 110 111 112 113 103 102 101 100 200 201 202 203 213 212 211 210 220 221 222 223 233 232 231 230 330 331 332 333 323 322 321 320 310 311 312 313 303 302 301 300
It's 2 days that I'm trying to find a solution and nothing so far. Java, C++ or pseudocode for a solution it's ok. Thanks
The problem is actually like counting in base sizeof(set) on length k (assuming the set has 10 items maximum).
For instance, with a set of
{ 0, 1, 2 }
on length 2, you count from00
to22
, base 3.To solve the "one digit change only" constraint, instead of counting increasingly, do that only until the next 10th change. Then count decreasingly, then again increasingly etc...
For instance in the example above
On length 3, keep the same reasoning, change the next 10th then go up or down depending on the initial value of the current digit
A recursive algorithm is one approach. The function depth 0 takes care of the first (left) digit, i.e. the highest 10th, and count up or down depending on its current digit state. If
0
, count up, and down otherwise. For each state, before incrementing, the function calls itself recursively with the next (right) digit status (which is either0
or the last item in the set). The maximal depth being the length k.Keep the digits status in an array of length k. Array is initialized to
{0 ... 0}
. Give the function the index in the array (starting with 0). For each iteration, if we're at max depth (iei == k-1
), print the array ; otherwise call recursively the function withi+1
.Pseudo code
This what you should get for
N = 3, and k = 4
Note that you should always get Nk numbers...
This is the C code that generated the above:
in
main()
initializeN
andk
and callAn iterative version, that does basically the same thing