How do I generate all permutations of k items selected from an array of n items?

However, I can't do this permutation using an auxiliary vector with 6 positions, so the algorithm is only varying the characters of [a..f], how can I make it vary all positions?

The code below generates all permutations of the first k items in the array. How do I expand it to generate all permutations of all selections of k items from n items?

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

void exchange(char v[], int i, int j)
{
    int aux = v[i];
    v[i] = v[j];
    v[j] = aux;
}

void permutation(char v[], int inf, int sup)
{
    if(inf == sup)
    {
        for(int i = 0; i <= sup; i  )
            printf("%c ", v[i]);
        printf("\n");
    }
    else
    {
        for(int i = inf; i <= sup; i  )
        {
            exchange(v, inf, i);
            permutation(v, inf   1, sup);
            exchange(v, inf, i); // backtracking
        }
    }
}

int main()
{
    char v[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
    int n = 6;

    permutation(v, 0, n-1);

    return 0;
}

CodePudding user response：

All you need to do is let your loop that is swapping the element at the current position sample from the entire input array instead of just the first six positions and change the termination condition to run to the desired output size instead of one less than that. (One less works when the output size equals the input size because once the first n−1 elements have been determined, the last element is necessarily the single remaining element that is not in the first n-1. But when we are selecting from a larger set, we must also choose the n^th element.)

So the following code works. I have set it to demonstrate with a reasonable size, as the case you give will have 1,168,675,200 lines of output.

#include <stdio.h>


void exchange(char v[], int i, int j)
{
    char aux = v[i];
    v[i] = v[j];
    v[j] = aux;
}

void permutation(char v[], int Position, int OutputSize, int InputSize)
{
    if (Position == OutputSize)
    {
        for (int i = 0; i < OutputSize;   i)
            printf("%c ", v[i]);
        printf("\n");
    }
    else
    {
        for(int i = Position; i < InputSize; i  )
        {
            exchange(v, Position, i);
            permutation(v, Position 1, OutputSize, InputSize);
            exchange(v, Position, i);
        }
    }
}


//  Produce the number of elements in an array.
#define NumberOf(a) (sizeof (a) / sizeof *(a))


int main(void)
{
#if 0
    char v[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
    int n = 6;

    permutation(v, 0, n, NumberOf(v));
#else
    char v[] = { 'a', 'b', 'c', 'd', 'e' };
    permutation(v, 0, 3, NumberOf(v));
#endif

    return 0;
}

(Note there are more efficient permutation algorithms; I have provided only a simple modification of the original code.)