2

The problem is simple. From given set of digits (there are max 10 digits), compute all numbers that can be madeform this digits (a digit can be used as many times it's is included in the set).

Fist I think of using brute force and running through all possible combinations, but the number of combinations is as big as factorial of N, where N is the number of digits. And even if it's possible how can I run though all possible combinations withouit using 10 for loops?

Second I tried to put all those digits in a string and the erasing one from the string and putting on the end and keep trying like this, but this probably won't give any possible combinations and even if it does I don't believe it'll be in a reasonable time.

I'm sure there must be a quicker and better algorithm for getting all possibles nubmers from a given set of digits.

I found one code on th Internet and it's:

#include <iostream>
#include <algorithm>
using namespace std;
int main () {
    int noOfDigits;
    cin >> noOfDigits;
  int myints[noOfDigits];
  for(int i = 0; i<noOfDigits; i++)
  {
      cin >> myints[i];
  }

  sort (myints,myints+3);
  do {
        for(int i = 0; i<noOfDigits;i++)
        {
            cout << myints[i];
        }
        cout << endl;
  } while ( next_permutation(myints,myints+noOfDigits) );
  return 0;
}
Stefan4024
  • 694
  • 1
  • 10
  • 21
  • Are you allowed to put the same digit at different position? For example, given {1,2}, can you do 11, 12,22,21? I mean is the same digit allowed to be selected more than once? – taocp Mar 31 '13 at 20:16
  • @SongWang I guess if it was included twise {1,1,2,2} in your case. – mlt Mar 31 '13 at 20:17
  • 4
    possible duplicate of [C++ algorithm for N! orderings](http://stackoverflow.com/questions/2141929/c-algorithm-for-n-orderings) – John Kugelman Mar 31 '13 at 20:18
  • @Stefan4024 Do you need a number of combinations? Or actually combinations? – mlt Mar 31 '13 at 20:18
  • No, for {1,2}, you should print or put in a vector just 12 and 21. I think I have state that in the question – Stefan4024 Mar 31 '13 at 20:19

1 Answers1

0

My approach might seem a bit convoluted but I'll give an overview and a very simple bit of sample code (from the wrong language) first.

As you say you fundamentally want all the permutations of your elements. So the obvious approach would be to use a library function which already does this. Perhaps std::next_permutation (I'll use intertools.permutations for my simple example). However you specify that you might have duplicate elements among your input set, which violates the constraint on that tool.

So my approach would be to build a mapping between a set of unique keys and our elements (digits) with their possible duplicates. For the small number of digits that you describe the easiest would be to use single characters as keys, mapping them (through a dictionary, of course) to the given elements (digits). A convenient way to do that is through string.printable. So given a tuple, list or other sequence of "digits" called mydigits we can build our mapping as:

#!python
import string
digit_mapping = dict([(y,x) for x,y in zip(mydigits,string.printable)])

From there all we have to do is iterate over the permutations and map the keys back to their original "digits" (in this case the string representation of those "digits"

#!python
for i in itertools.permutations(digit_mapping.keys()):
    perm = ''.join([str(digit_mapping[x]) for x in i])
    print perm,

... of course you might have to work it a little differently if you wanted to print these permutations in some particular order rather than in whatever the .keys() method and the itertools.permutations() function does. (Those are implementation details).

So, can you create such a mapping, iterate over the permutation of its keys, and perform the map dereferencing as you return/print your results?

Jim Dennis
  • 17,054
  • 13
  • 68
  • 116