Permutation in vectors of different size

Question

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;
}

Why not shuffle the array with [Fisher Yates Shuffle](https://stackoverflow.com/q/42321370/3422102) or just choose a random char with `char c = v[rand() % 36];`? If you shuffle, you can just take the first 6 from `v[]`. If you use a random index, you need to loop to ensure you don't have duplicate random numbers appear. — David C. Rankin, Aug 25 '22 at 01:22
Because I need to generate all possible strings of 6 characters using the elements of key[] and none of these elements can be repeated, besides that I want to use this recursive backtraking logic. — Legendary Legend, Aug 25 '22 at 01:30

score 1 · Accepted Answer · answered Aug 25 '22 at 02:08

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.)

Thanks it worked, now I'm trying to make the program test only passwords that have, by the two letters and two numbers, but I don't want to loop in the vector, I thought of doing the following send the current number count as a parameter of the backtracking function (this way , it would be enough to test the current number and add it to what is already received by the function). Something similar must be done with the letters, but I'm not able to implement it, can you help me? — Legendary Legend, Aug 25 '22 at 14:43

Permutation in vectors of different size

1 Answers1