Derive the entire permutation of length k that can be formed from a set of n characters?

Question

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 only one char replacement 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 

It 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 should work 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 is 2 days that I am trying to find a solution and nothing so far. Java, C ++ or pseudo-code for the solution, this is normal. Thanks

Answer 1

The problem is actually similar to counting in base sizeof (set) by length k (assuming the set has a maximum of 10 elements).

For example, when typing { 0, 1, 2 } along a length of 2, you count from 00 to 22 , base 3 ..

In order to solve the “only unambiguous change” restriction, instead of counting it more and more often, do this only until the next change of 10 ^th . Then decrease the score, then again more often, etc.

For example, in the example above

 00 -> 02 then increase the next tenth (12), then count downward 12 -> 10 then again +10 to get 20, then go up again 20 -> 22 

At length 3, keep the same reasoning, change the next 10 ^th then go up or down depending on the initial value of the current digit

 000 -> 002, 012 -> 010, 020 -> 022 122 -> 120, 110 -> 112, 102 -> 100 200 -> 202, 212 -> 210, 220 -> 222 

A recursive algorithm is one approach. Function depth 0 processes the first (left) digit, i.e. The highest is 10 ^th and counts up or down depending on the current state of the digit. If 0 , count otherwise. For each state, before the increment, the function calls itself recursively with the next (right) digital status (which is either 0 or the last element in the set). Maximum depth is length k.

Save the status of digits in an array of length k. The array is initialized to {0 ... 0} . Give the function the index in the array (starting at 0). For each iteration, if we are at maximum depth (i.e. i == k-1 ), print an array; otherwise call the recursive function with i+1 .

Pseudo code

 k length of number (number of digits) N size of set (1 .. 10), values from 0 to N-1 A array of size k A[0 .. k-1] = 0 function f ( i ) begin inc = -1 if (A[i] > 0), 1 otherwise # Increment end = 0 if (A[i] > 0), N-1 otherwise # Max value j is the counter j = A[ i ] # Init while ( (inc<0 AND j>=end) OR (inc>0 AND j<=end) ) do A[ i ] = j if (i < k-1) call f ( i+1 ) otherwise print array A j = j + inc done end call f ( 0 ) 

This is what you should get for N = 3, and k = 4

 0000 0001 0002 0012 0011 0010 0020 0021 0022 0122 0121 0120 0110 0111 0112 0102 0101 0100 0200 0201 0202 0212 0211 0210 0220 0221 0222 1222 1221 1220 1210 1211 1212 1202 1201 1200 1100 1101 1102 1112 1111 1110 1120 1121 1122 1022 1021 1020 1010 1011 1012 1002 1001 1000 2000 2001 2002 2012 2011 2010 2020 2021 2022 2122 2121 2120 2110 2111 2112 2102 2101 2100 2200 2201 2202 2212 2211 2210 2220 2221 2222 

Please note that you should always get N ^k ...

---

This is the C code that generated above:

 int a[20] = {0}; // Put here the right size instead of 20, or use #define... int N,k; void f(int i) { int inc = a[i] ? -1:1; int end = a[i] ? 0:N-1; int j; for(j=a[i] ; inc<0 && j>=end || inc>0 && j<=end ; j+=inc) { a[i] = j; if (i < k-1) f(i+1); else { int z; for(z=0 ; z<k ; z++) printf("%d", a[z]); printf("\n"); } } } 

in main() initialize N and k and call

 f(0); 

---

Iterative version that does basically the same thing

 void fi() { int z,i,inc[k]; for(i=0 ; i<k ; i++) { a[i] = 0; // initialize our array if needed inc[i] = 1; // all digits are in +1 mode } int p = k-1; // p, position: start from last digit (right) while(p >= 0) { if (p == k-1) { for(z=0 ; z<k ; z++) printf("%d", a[z]); printf("\n"); } if (inc[p]<0 && a[p]>0 || inc[p]>0 && a[p]<N-1) { a[p] += inc[p]; p = k-1; } else { inc[p] = -inc[p]; p--; } } } 

Answer 2

You just change the iteration direction of your least significant element. If you create permutations in a container, you can invert the order of size(set) permutations for each other size(set) permutation.

An alternative is to write your own permutation generator that takes care of this for you. For example, in C ++, a simple permutation generator and printer look like this:

 vector<vector<int>::const_iterator> its(k, cbegin(set)); do { transform(cbegin(its), cend(its), ostream_iterator<int>(cout), [](const auto& i) { return *i; }); cout << endl; for (auto it = rbegin(its); it != rend(its) && ++*it == cend(set); ++it) *it = cbegin(set); } while (count(cbegin(its), cend(its), cbegin(set)) != k); 

Live example

The modification you would need to do would be to alternate the direction of the iteration of the least significant iterator each time it reaches the end of the set, something like this:

 vector<vector<int>::const_iterator> its(k, cbegin(set)); vector<bool> ns(k); for(int i = k - 1; its.front() != cend(set); its[i] = next(its[i], ns[i] ? -1 : 1), i = k - 1) { transform(cbegin(its), cend(its), ostream_iterator<int>(cout), [](const auto& i) { return *i; }); cout << endl; while (i > 0 && (!ns[i] && its[i] == prev(cend(set)) || ns[i] && its[i] == cbegin(set))) { ns[i] = !ns[i]; --i; } } 

Live example