Listing all permutations of digits without repeating in C language

Viewed 3521

So I have this assignment question in C language which I have worked on for last 5 hours but can't figure out what's wrong.

Problem Statement:

Take n as number of digits from 1 to 9 and prints all the possible numbers formed without repeating digits. For E.g. If n = 3, then digits are 1,2,3 and numbers are 123, 132, 231, 213, 321, 312.

Input: 2 Output: 12, 21

Input: 3 Output: 123, 132, 231, 213, 321, 312

This is what I have done so far:

#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 10

void print(int *num, int n)
{
    int i;
    for ( i = 0 ; i < n ; i++){
        printf("%d", num[i]);
    }
    printf("\n");
}

int main()
{
    int num[N];
    int temp;
    int i, n, j,k;

    printf("\nNo of digits? : ");
    scanf("%d", &n);

    for(k=0; k<n; k++){
        num[k] = k + 1; 
    }

    for (j = 1; j <= n; j++) {
        for (i = 0; i < n-1; i++) {
            temp = num[i];
            num[i] = num[i+1];
            num[i+1] = temp;
            print(num, n);
        }
    }
    return 0;
}

I am getting expected result for digits upto 3. But from 4 it's not showing all permutations of digits.

No of digits? : 4

2134
2314
2341
3241
3421
3412
4312
4132
4123
1423
1243
1234

On setting counter to go till n! array will be out of index.

So how to correctly count all permutations ?

1 Answers

What am I missing ?

The number of possibilities to order n elements is factorial(n), your two imbricated for cannot compute factorial(n) for any value of n so they cannot find all the orders.


a possible solution is :

#include <stdio.h>

/* current is the number under fabrication 
   max is the max number of digit and also the max digit to use
   n is the number of digits to add to current
   used[n] is 0 if the digit n is not yet used, else 1 */

void permut(unsigned current, unsigned max, unsigned n, int used[])
{
  if (n == 0)
    printf("%d\n", current);
  else {
    unsigned i;

    for (i = 1; i <= max; ++i) {
      if (!used[i]) {
        used[i] = 1;
        permut(current*10 + i, max, n - 1, used);
        used[i] = 0;
      }
    }
  }
}

int main()
{
  unsigned n;
  int used[10] = { 0 }; /* used[n] is 0 if the digit n is not yet used */

  printf("No of digits? : ");
  if ((scanf("%u", &n) != 1) || (n == 0) || (n > 9))
    return 0;

  permut(0, n, n, used);
  return 0;
}

for 2 :

12
21

for 3 :

123
132
213
231
312
321

for 4 :

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
Related