Print all 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 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

Answer 1

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 from 00 to 22, base 3.

To solve the "one digit change only" constraint, instead of counting increasingly, do that only until the next 10^th change. Then count decreasingly, then again increasingly etc...

For instance 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

On 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. The function depth 0 takes care of the first (left) digit, i.e. the highest 10^th, 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 either 0 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 (ie i == k-1), print the array ; otherwise call recursively the 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 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

Note that you should always get N^k numbers...

---

This is the C code that generated the 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);

---

An 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're just changing the iteration direction of your least significant element. If you're generating the permutations to a container you can invert the order of size(set) permutations every other size(set) permutations.

The 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 would 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 make would be to alternate the iteration direction of the least significant iterator each time it reached an 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