The Countdown QuickPerm Algorithm (Tail):
(Formally EXAMPLE_02)

EXAMPLE 02 - Tail Permutations Using a Linear Array Without Recursion

// NOTICE: Copyright 1991-2010, Phillip Paul Fuchs #define N 12 // number of elements to permute. Let N > 2 void example_02(void) { const unsigned int ax = N - 1; // constant index ceiling (a[N] length) unsigned int a[N], p[N+1]; // target array and index control array register unsigned int i, j, tmp; // index variables and tmp for swap for(i = 0; i < N; i++) // initialize arrays; a[N] can be any type { a[i] = i + 1; // a[i] value is not revealed and can be arbitrary p[i] = i; } p[N] = N; // p[N] > 0 controls iteration and the index boundary for i //display(a, 0, 0); // remove comment to display initial array a[] i = 1; // setup first swap points to be ax-1 and ax respectively (i & j) while(i < N) { p[i]--; // decrease index "weight" for i by one j = ax - i % 2 * p[i]; // IF i is odd then j = ax - p[i] otherwise j = ax i = ax - i; // adjust i to permute tail (i < j) tmp = a[j]; // swap(a[i], a[j]) a[j] = a[i]; a[i] = tmp; //display(a, i, j); // remove comment to display target array a[] i = 1; // reset index i to 1 (assumed) while (!p[i]) // while (p[i] == 0) { p[i] = i; // reset p[i] zero value i++; // set new index value for i (increase by one) } // while(!p[i]) } // while(i < N) } // example_02()

EXAMPLE 02a - Function to Display Permutations (Optional)

// NOTICE: Copyright 1991-2010, Phillip Paul Fuchs void display(unsigned int *a, unsigned int i, unsigned int j)                   { for(unsigned int x = 0; x < N; x++) printf("%d ",a[x]); printf(" swapped(%d, %d)\n", i, j); getch(); // press any key to continue... } // display()

Fundamental Analysis of Permutation Example 02 Above

Number of Objects to Permute (N)	a[N] Display of Initial Sequence	a[N] Display of Final Sequence	Total Number of Unique Combinations Produced (N!)
3	1 2 3	3 2 1	2 * 3 = 6
4	1 2 3 4	2 3 4 1	6 * 4 = 24
5	1 2 3 4 5	5 2 3 4 1	24 * 5 = 120
6	1 2 3 4 5 6	2 5 6 3 4 1	120 * 6 = 720
7	1 2 3 4 5 6 7	7 2 3 4 5 6 1	720 * 7 = 5040
8	1 2 3 4 5 6 7 8	2 7 8 3 4 5 6 1	5040 * 8 = 40320
9	1 2 3 4 5 6 7 8 9	9 2 3 4 5 6 7 8 1	40320 * 9 = 362880
if N is even	1 2 3 . . . (N - 1) N	2 (N - 1) N 3 4 . . . (N - 2) 1	(N - 1)! * N = N!
if N is odd	1 2 3 . . . (N - 1) N	N 2 3 . . . (N - 1) 1	(N - 1)! * N = N!

Next is EXAMPLE 03 which inclusively reverses elements from index j to index i. (Head Reversals)

Copyright © 2024 by Phillip Paul Fuchs, all rights reserved.
Abstracting with credit is permitted...