Search
Next: 0.5.2.2 References Up: 0.5.2 Permutations Previous: 0.5.2 Permutations

### 0.5.2.1 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);
}
```

Scott Gasch
1999-07-09