Listing all permutations of digits without repeating in C language

Question

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 ?

Your program does not create the output you claim. Please never ever modify the output by sorting etc. Instead show us what the program really prints. And of course also show us the wrong output. Not only the correct cases. — Gerhardh, Jan 09 '19 at 07:32
backtracking is a way, if you're interested in iterative solution: https://www.geeksforgeeks.org/johnson-trotter-algorithm/ — some user, Jan 09 '19 at 07:36
I disagree with the duplicate mark, the problem here is more simple, the solution for "Print all permutation in lexicographic order" are more complicated and must not be followed for the current problem — bruno, Jan 09 '19 at 08:14

bruno · Answer 1 · 2019-01-09T08:08:07.917

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 :

for 4 :

Forgot to mention that I am aware of it. I will add it. My questions is how to correct it ? — Rahul, Jan 09 '19 at 07:30
@user101 I hoped you can found by yourself from my remark about fact, anyway I edited my answer with a proposal — bruno, Jan 09 '19 at 07:46
@user101 I added comments to explain the role of the variables, if you still cannot understand please execute it under a debugger, the algorithm is trivial — bruno, Jan 09 '19 at 08:10

Listing all permutations of digits without repeating in C language

1 Answers1