Generating k permutations from n in C

Question

I basically need the equivalent result of the following Python itertools command in C:

a = itertools.permutations(range(4),2))

Currently my process involves first "choosing" 5 elements from 10 then generating permutations for those 5 elements as shown here

The issue with this approach is the order of the outputs. I need it to be (a), while what i get is (b), shown below.

a = itertools.permutations(range(4),2)
for i in a:
    print(i)

(0, 1)
(0, 2)
(0, 3)
(1, 0)
(1, 2)
(1, 3)
(2, 0)
(2, 1)
(2, 3)
(3, 0)
(3, 1)
(3, 2)

b = itertools.combinations(range(4),2) 
for i in b:
    c = itertools.permutations(i)
    for j in c:
        print(j)
(0, 1)
(1, 0)
(0, 2)
(2, 0)
(0, 3)
(3, 0)
(1, 2)
(2, 1)
(1, 3)
(3, 1)
(2, 3)
(3, 2)

An alternate approach which I am using is as follows

void perm(int n, int k)
{
    bool valid = true;
    int h = 0, i = 0, j = 0, limit = 1;
    int id = 0;
    int perm[10] = { 0,0,0,0,0,0,0,0,0,0 };
    for (i = 0; i < k; i++)
        limit *= n;
    for (i = 0; i < limit; i++)
    {
        id = i;
        valid = true;
        for (j = 0; j < k; j++)
        {
            perms[j] = id % n;
            id /= n;
            for (h = j - 1; h >= 0; h--)
                if (perms[j] == perms[h])
                {
                    valid = false; break;
                }
            if (!valid) break;
        }
        if (valid)
        {
            for (h = k - 1; h > 0; h--)
                printf("%d,", perms[h]);
            printf("%d\n", perms[h]);
            count++;
        }
    }
}

Memory is my constraint, so I cannot store the permutations indefinitely. Performance needs to be better than the algorithm above, as when n is 50 and k is 10, I end up iterating through more invalid combinations(60+%)

I am aware of Heap's algorithm for generating permutations in place but again it generates for entire array not k of n like I need.

Questions.

1. Is there a better way to do this than iterate n^k times?
2. Can I make a lazy iterator which moves to next permutation given current permutation?

EDIT this is not a duplicate of std::next_permutation implementation as that will permute and entire range of the input. I have clearly mentioned i need k of n permutation .ie if my range is 10 I want all permutations of a length (k) say 5, std::next_permutation works when length or permutation is same as length of input range

UPDATE Here is an ugly recursive NextPerm solution which is about 4 times faster than my older solution and gives the incremental nextPerm like a Python lazy iterator.

int nextPerm(int perm[], int k, int n)
{
    bool invalid = true;
    int subject,i;
    if (k == 1)
    {
        if (perm[0] == n - 1)
            return 0;
        else { perm[0]=perm[0]+1; return 1; }
    }
    subject = perm[k - 1]+1;
    
    while (invalid)
    {
        if (subject == n)
        {
            subject = 0;
            if (!nextPerm(perm, k - 1, n))
                return 0;
        }
        for (i = 0; i < k-1; i++)
        {
            if (perm[i] != subject)
                invalid = false;
            else
            {
                invalid = true;subject++; break; 
            }
        }
    }
    perm[k - 1] = subject;
    return 1;
}
int main()
{
    int a, k =3 ,n = 10;
    int perm2[3] = { 0,1,2}; //starting permutation
    unsigned long long count = 0;
    int depth = 0;
    do
    {
        for (a = 0; a < k - 1; a++)
            printf("%d,", perm2[a]);
        printf("%d\n", perm2[k - 1]);
        count++;
    }
    while (nextPerm(perm2,k,n));
    printf("\n%llu", count);
    getchar();
    return 0;
}

Answer 1

There are simple modification to the standard permutation algorithms which will produce k-permutations.

Lexicographically-ordered permutations (aka std::next_permutation)

In C++, k-permutations can be generated by the simple expedient using std::next_permutation, and just reversing the n-k-suffix of the permutation before each call to std::next_permutation.

It's reasonably clear how that works: the algorithm generates permutations in order, so the first permutation starting with a given prefix has the remaining suffix in increasing order, and the last permutation with the same prefix has its suffix in decreasing order. Decreasing order is simply the reverse of increasing order, so a single call to std::reverse is sufficient.

The lexicographical order next-permutation algorithm is very simple:

1. Search backwards from the end for an element which could be increased by swapping it with some later element.

2. Once the rightmost such element is found, find the smallest following element with which it could be swapped, and swap them.

3. Sort the new suffix into increasing order (by reversing it, since it was previously in decreasing order).

An advantage of the lexicographical algorithm is that it transparently handles arrays with repeated elements. As long as the number of repetitions of any given element is O(1), next-permutation is amortized O(1) (per call), and in the worst case it is O(n). When generating k-permutations, the extra flip causes the cost of next_k_permutation to be O(n-k), which is effectively O(n) if k is fixed. That's still reasonably fast, but not as fast as non-iterative algorithms which can maintain state instead of doing the search in step 1 to figure out which element to move.

The following C implementation is equivalent to std::reverse(); std::next_permutation(); (except that it swaps before reversing):

#include <stddef.h>

/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
  int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
  for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}

/* Given an array of n elements, finds the next permutation in
 * lexicographical order with a different k-prefix; in effect, it 
 * generates all k-permutations of the array.
 * It is required that the suffix be sorted in ascending order. This
 * invariant will be maintained by the function.
 * Before the first call, the array must be sorted in ascending order.
 * Returns true unless the input is the last k-permutation.
 */ 
int next_k_permutation(int* elements, size_t n, size_t k) {
  // Find the rightmost element which is strictly less than some element to its
  // right.
  int tailmax = elements[n - 1];
  size_t tail = k;
  while (tail && elements[tail - 1] >= tailmax)
    tailmax = elements[--tail];
  // If no pivot was found, the given permutation is the last one.
  if (tail) {
    size_t swap_in;
    int pivot = elements[tail - 1];
    // Find the smallest element strictly greater than the pivot, either
    // by searching forward from the pivot or backwards from the end.
    if (pivot >= elements[n - 1]) {
      for (swap_in = tail; swap_in + 1 < k && elements[swap_in + 1] > pivot; ++swap_in) {}
    } else {
      for (swap_in = n - 1; swap_in > k && elements[swap_in - 1] > pivot; --swap_in) {}
    }
    // Swap the pivots
    elements[tail - 1] = elements[swap_in];
    elements[swap_in] = pivot;
    // Flip the tail. 
    flip(elements, k, n);
    flip(elements, tail, n);
  }
  return tail;
}

Here's a simple driver and a sample run:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int intcmp(const void* a, const void* b) {
  return *(int*)a < *(int*)b ? -1 : 
         *(int*)a > *(int*)b ?  1 :
                                0 ;
}

int main(int argc, char** argv) {
  size_t k = (argc > 1) ? atoi(argv[1]) : 0;
  if (argc < k + 2) {
    fprintf(stderr, "Usage: %s K element...\n"
                    "       where K <= number of elements\n",
                    argv[0]);
    return 1;
  }
  size_t n = argc - 2;
  int elements[n];
  for (int i = 0; i < n; ++i) elements[i] = atoi(argv[i + 2]);
  qsort(elements, n, sizeof *elements, intcmp);
  do {
    const char* delimiter = "";
    for (size_t i = 0; i < k; ++i) {
      printf("%s%2d ", delimiter, elements[i]);
      delimiter = " ";
    }
    putchar('\n');
  } while (next_k_permutation(elements, n, k));
  return 0;
}

Sample run (with repeated element):

$ ./k_next_permutation 2 7 3 4 4 5
 3   4 
 3   5 
 3   7 
 4   3 
 4   4 
 4   5 
 4   7 
 5   3 
 5   4 
 5   7 
 7   3 
 7   4 
 7   5 

Modified Heap's algorithm

As an example of an algorithm which maintains state, Heap's algorithm can be easily modified to produce k-permutations. The only change is that when the algorithm recurses down to position n - k, the k-suffix is reported as the k-permutation and the (n-k)-prefix is transformed the way the Heap algorithm would transform it if it were run to conclusion: the prefix reversed if its length is odd and rotated one to the left if its length is even. (That's a big hint about how Heap's algorithm works, by the way.)

Using the recursive algorithm is a bit annoying because it doesn't really allow incremental permutations. However, it's simple to follow. Here, I've just passed a functor into the recursive procedure which is called with each permutation in turn.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>

/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
  int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
  for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}
static void rotate_left(int* elements, size_t lo, size_t hi) {
  if (hi > lo) {
    int tmp = elements[lo];
    for (size_t i = lo + 1; i < hi; ++i) elements[i - 1] = elements[i];
    elements[hi - 1] = tmp;
  }
}

/* Recursive function; the main function will fill in the extra parameters */
/* Requires hi >= lo and hi >= k. Array must have size (at least) lo + k */    
static bool helper(int* array, size_t lo, size_t k, size_t hi,
                       bool(*process)(void*, int*, size_t), void* baton) {
  if (hi == lo) {
    if (!process(baton, array + lo, k)) return false;
    if (lo % 2)
      flip(array, 0, lo);
    else
      rotate_left(array, 0, lo);
  }
  else {
    for (size_t i = 0; i < hi - 1; ++i) {
      if (!helper(array, lo, k, hi - 1, process, baton))
        return false;
      swap(array, hi % 2 ? 0 : i, hi - 1);
    }
    if (!helper(array, lo, k, hi - 1, process, baton))
      return false;
  }
  return true;
}

/* Generate all k-permutations of the given array of size n.
 * The process function is called with each permutation; if it returns false,
 * generation of permutations is terminated.
 */ 
bool k_heap_permute(int* array, size_t n, size_t k,
                    bool(*process)(void*, int*, size_t), void* baton) {
  assert(k <= n);
  return helper(array, n - k, k, n, process, baton);
}

Here's an example of its use:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool print_array(void* vf, int* elements, size_t n) {
  FILE* f = vf;
  const char* delim = "";
  for (size_t i = 0; i < n; ++i) {
    fprintf(f, "%s%2d", delim, elements[i]);
    delim = " ";
  }
  putc('\n', f);
  return true;
}

int main(int argc, char** argv) {
  size_t k = (argc > 1) ? atoi(argv[1]) : 0;
  if (argc < k + 2) {
    fprintf(stderr, "Usage: %s K element...\n"
                    "       where K <= number of elements\n",
                    argv[0]);
    return 1;
  }
  size_t n = argc - 2;
  int elements[n];
  for (int i = 0; i < n; ++i)
    elements[i] = atoi(argv[i + 2]);
  k_heap_permute(elements, n, k, print_array, stdout);
  return 0;
}

Sample run:

$ ./permut 2      1 5 9 7 3
 7  3
 9  3
 5  3
 1  3
 1  5
 7  5
 9  5
 3  5
 3  9
 1  9
 7  9
 5  9
 5  7
 3  7
 1  7
 9  7
 9  1
 5  1
 3  1
 7  1