ccan

Browse Source Download (without any required ccan dependencies)

Module:

permutation

Summary:

Generate permutations

Dependencies:

Description:

This module allows you to generate all permutations of a given number of elements. It can also modify a user-supplied array in place through all those permutations.

It uses the "plain changes" method, aka the Steinhaus-Johnson-Trotter algorithm to generate the permtations. This has some advantages over a naive recursive algorithm:

- Each permutation is generated from the last by a single swap of

  adjacent elements

- Constructing each permutation in place from the last takes

  amortized O(1) time.

Example:

// Given "1 2 3" outputs 1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3
#include <stdio.h>
#include <ccan/permutation/permutation.h>

int main(int argc, char *argv[])
{
        int i;
        struct permutation *pi = permutation_new(argc - 1);

        do {
                for (i = 1; i < argc; i++)
                        printf("%s ", argv[i]);
                printf("\n");
        } while (permutation_change_array(pi,
                 &argv[1], sizeof(argv[1])));
        exit(0);
}

License: