Permutations
Imagine we have a collection of n distinct objects. There are n! ways to
order these objects; that is, we can form n! different arrangements of
these n objects. This is true because any such arrangement will consist
of n items, no matter which happens to be first. To choose the first
object in a particular arrangement we have n options. However, to choose
the second object after already having placed the first, we are left
with one less choice. The first object is fixed at this point. Thus, we
have (n-1) alternatives. As we place more and more objects we have less
and less choices of objects to place. The summation below follows from
this discussion:
This is the same as n!.
This section presents an algorithm for calculating all possible
permutations (that is, not just the number of permutations but the
actual permutated data) given the number of distinct data items to be
arranged.
Source Code
References
Scott Gasch
Algorithms_Archive/node106.html100444 0 0 10752 7022137323 14773 0ustar rootroot
Next: References Up: Permutations Previous: Permutations
Source Code
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100
//
// A single call to permut(k, n) will produce (n - k + 1)!
// permutations consisting of the integers:
//
// r[1] ... r[k-1] ... r[k] ... r[n]
//
// In the output, the first r[1]...r[k-1] numbers will not
// change. The r[k]...r[n] numbers will be permiated. An
// initial call of permut(1, n) will produce the full n!
// permutations of these n numbers.
//
//
void permut(int k, int n, int *nums)
{
int i, j, tmp;
/* when k > n we are done and should print */
if (k <= n)
{
for (i = k; i <= n; i++)
{
/**
* each element i is promoted to the kth place while the rest
* of the items from k to i-1 are shifted to make room with
* a ripple-shift operation.
*
**/
tmp = nums[i];
for (j = i; j > k; j--)
{
nums[j] = nums[j-1];
}
nums[k] = tmp;
/* recurse on k+1 to n */
permut(k + 1, n, &(nums[0]));
for (j = k; j < i; j++)
{
nums[j] = nums[j+1];
}
nums[i] = tmp;
}
}
else
{
for (i = 1; i <= n; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
}
}
int main(void)
{
int iCount;
int rgNums[MAX_NUM];
int i;
printf("Enter n: ");
scanf("%d", &iCount);
/* create a workspace of numbers in their respective places */
for (i = 1; i <= iCount; i++)
{
rgNum[i] = i;
}
printf("Permutations:\n");
permut(1, iCount, rgNum);
}