Permutation of a number's digits

Question

Consider number 194 declared as type int Is it possible to obtain it's digits permutations like other ints efficiently?
Number: 194
419 int
491 int
914 int
941 int

I am using the next_permutation however it only works with arrays. So I thought it wouldn't be wise to convert int to an int array (?!) then obtain the permutation as an array and convert it to it.

Any suggestions?

I dont think convert an int to an int array then finding a permutation array and converting back to int makes sense. Although, if I can't find any solutions that's what I'll do — Ali, Jan 28 '12 at 23:51
I don't think you can do anything better than [link](http://stackoverflow.com/a/1397766/369872) breaking your int into digits and using next_permutation — David, Jan 28 '12 at 23:54

score 3 · Accepted Answer · answered Jan 29 '12 at 00:01

Permuting the digits is basically a string-operation, not a (simple) mathematical operation. Converting to an array (string) and then using next_permutation() sounds more sensible than trying to do it mathematically.

Here's the mathematical version - without intermediate values saved:

int a = 194;
int b = (a / 100)       * 100 + (a % 10)        * 10 + ((a / 10) % 10) * 1; // 149
int c = (a % 10)        * 100 + ((a / 10) % 10) * 10 + (a / 100)       * 1; // 491
int d = (a % 10)        * 100 + (a / 100)       * 10 + ((a / 10) % 10) * 1; // 419
int e = ((a / 10) % 10) * 100 + (a / 100)       * 10 + (a % 10)        * 1; // 914
int f = ((a / 10) % 10) * 100 + (a % 10)        * 10 + (a / 100)       * 1; // 941

With intermediate values, it's a little easier to see what's going on (except that I generated different assignments for b through f this time).

int a = 194;
int d1 = a / 100;
int d2 = (a / 10) % 10;
int d3 = a % 10;

int a = d1 * 100 + d2 * 10 + d3 * 1; // 194
int b = d1 * 100 + d3 * 10 + d2 * 1; // 149
int c = d2 * 100 + d1 * 10 + d3 * 1; // 914
int d = d2 * 100 + d3 * 10 + d1 * 1; // 941
int e = d3 * 100 + d1 * 10 + d2 * 1; // 419
int f = d3 * 100 + d2 * 10 + d1 * 1; // 491

Use the next_permutation() mechanism; it will generalize to 4-digit and 5-digit and N-digit numbers where this will not.

Thanks for the great answer, I'll try the string conversion – Ali Jan 29 '12 at 00:04 — Ali, Jan 29 '12 at 00:04

ose · Answer 2 · 2012-01-29T00:05:35.603

Getting the permutations of the decimal digits will require you to interact with the number as a decimal, so power-of-2 manipulations are probably not going to help much here.

My suggestion would be:

1. Convert number to string
2. Set up the string as a circular buffer
3. Step through the buffer progressively (each increment of the index into the circular buffer will give you one permutation)
4. Reconstruct the number from the "new" arrangement of the characters representing the digits
5. Repeat for the length of the string.

Unless you are running in a slow/resource-constrained environment, I wouldn't try to overthink the problem beyond this.

Edit:

As pointed out in the comments this doesn't generate all permutations, to do so would require adding another step at the end where the process is repeated but with progressively larger increments to the index variable.

You don't generate all permutations. 419 -> 194 -> 941, but not 491 — James, Jan 28 '12 at 23:54

score 0 · Answer 3 · answered Jan 28 '12 at 23:52

0

You'd first have to extract each decimal place's value first: either by converting it to a character array (itoa()) or by writing a small for loop that divides the number by powers of 10. Once you have the digits separated, you can write a loop to generate the permutations.

answered Jan 28 '12 at 23:52

xxbbcc

16,930
5
50
83

so you do not advise next_permutation()? – Ali Jan 28 '12 at 23:58

Permutation of a number's digits

3 Answers3