[Solved] Print all permutation of length k that can be formed from a set of n characters?

by


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 10th 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 10th 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 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 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 Nk 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--;
        }
    }
}

8

solved Print all permutation of length k that can be formed from a set of n characters?