0

I want to generate every int containing 0,1,2,2,4,4 (or longs if the set is bigger). For a small amount of digits, it's easily feasible by hand, but I don't understand how I could do that.

For a not-so-big set of integer, like my sample, we could use something like:

for(i = 102244; i <= 442210; i++){
   //check if the digits are in the number
   //add it to a tree
}

But as you can see, for a bigger set, the complexity is far from the best we could do (O(10n), but I may be wrong). Do you have any hint on how to do this?

The sample is chosen randomly that's not homework!

This is my solution, but it's not really optimized for huge numbers, might help some people though:

@Test
public void testPossibleNumbers(){
    TreeSet<Long> possibleNumbers = new TreeSet<Long>();
    String a = "012244";
    permutation("",a,possibleNumbers);
    LOGGER.info("Array of possible numbers"); //breapoint: 150 solutions
}

private static void permutation(String prefix, String str, TreeSet<Long> tree) {
    int n = str.length();
    if (n == 0 && !prefix.startsWith("0")){
        tree.add(Long.parseLong(prefix));
    }
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), tree);
    }
}
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Fabinout
  • 878
  • 7
  • 25
  • @Fabinout: Just wanted to be clear. Also, how do you want to handle leading 0's? For your example, is 012244 a solution? – Codie CodeMonkey Jul 23 '13 at 08:06
  • @CodieCodeMonkey Of course, 012244 is not an Integer abiding to my laws ;) – Fabinout Jul 23 '13 at 08:08
  • btw, the for should start at 12244 – Stefano Falasca Jul 23 '13 at 08:26
  • @StefanoFalasca Nope, because 12244 doesn't contain a 0 – Fabinout Jul 23 '13 at 08:38
  • so (012244 != 12244) evaluates to true, ok. Jokes on the side, if these are your semantics, you should "adapt" my answer to them. – Stefano Falasca Jul 23 '13 at 08:40
  • 1
    [Here's some code to efficiently generate permutations without duplicates.](http://stackoverflow.com/a/17694628/1711796) Hint - To avoid numbers starting with 0, you need to add a simple check to the if-statement to make sure you don't put a 0 in the first position. – Bernhard Barker Jul 23 '13 at 12:49
  • @Dukeling Wow. Just Wooooow. I ran it and it gave me the permutations in less than a second (and I printed those permutations, so I pretty much only timed the System.out.println command). Thanks!! – Fabinout Jul 23 '13 at 13:44

2 Answers2

1

You simply enumerate all the permutations of the starting "set" (it's not a set really, it contains duplicates). Of course you might end up with some duplicates (since you didn't start from a set) and with numbers starting with (any number of) 0 (es), which you should take into account.

What I would do is use some kind of container (std::set in c++) which doesn't accept duplicates, then starting pushing numbers in it using permutations as in 012244 012244 012424 012442 ... 442210

Duplicates would be taken into account for by the container, the zero "issue" would not be a problem, since 0*10^5+1*10^4+...+2 doesn't keep track of the leading "0".

Stefano Falasca
  • 8,837
  • 2
  • 18
  • 24
1

I would start with a transformation of your data from a list with repetitions, to a dictionary that maps each of the 10 possible digits to the number of times it's available. Some entries will have the number of repetitions as 0, indicating that the digit is not to be used.

We'll proceed from left to right, so that we can take care of the business of not using a 0 in the left-most position.

1) For the left-most postion, build a candidate list of digits using the dictionary. Leave 0 out of this list. 2) Build the candidate list for the next place, considering the previous choices. Each candidate list gets placed on a stack.

For the data 0, 1, 2, 2, 4, 4 as given by the OP we build the following stack:

{4}        num = 102244
{4}        num = 10224_
{2, 4}     num = 1022__
{2, 4}     num = 102___ (0 and 1 are all used)
{0, 2, 4}  num = 10____ (since we've used all the ones)
{1, 2, 4}  num = 1_____ (since 0 is not allowed on the left)

3) Backtrack. Remove the first digit from the choice list at the top of the stack, it's already been used. Put the next choice in the appropriate slot of the integer. If there are no more choices, pop the stack until a choice can be made.

So after step 3 the stack looks like:

{4}        num = 1024__
{2, 4}     num = 102___ (0 and 1 are all used)
{0, 2, 4}  num = 10____ (since we've used all the ones)
{1, 2, 4}  num = 1_____ (since 0 is not allowed on the left)

4) Rebuild the stack as in steps 1 and 2.

{4}        num = 102424
{2, 4}     num = 10242_
{4}        num = 1024__
{2, 4}     num = 102___ (0 and 1 are all used)
{0, 2, 4}  num = 10____ (since we've used all the ones)
{1, 2, 4}  num = 1_____ (since 0 is not allowed on the left)

5) Continue this way until no more choices can be made.

Note that this method only emits valid numbers, and it does so with no repetitions.

Working python code:

data = [0, 1, 2, 2, 4, 4]
results = []

# Number of digits
n = len(data)

# initialize the counts
counts = dict((i, 0) for i in range(10))
for digit in data:
    counts[digit] += 1

# We use this to keep track of the digits that have been used
used = dict((i, 0) for i in range(10))


choice_stack = []

# This is where we'll store the digits
slots = []

first = True
while first or len(choice_stack) > 0:

    # build phase
    while True:
        choices = []
        for i in range(10):
            # no 0 allowed in the left-most place
            if i == 0 and first:
                first = False
                continue
            if counts[i] - used[i] > 0:
                choices.append(i)

        # Leave the build phase if we've used all of our digits
        if len(choices) == 0:
            break;

        choice_stack.append(choices)
        slots.append(choices[0])
        used[choices[0]] += 1

    # Compute the integer
    num = 0
    for i in range(n):
        num += 10**i * slots[-i - 1]
    results.append(num)

    # backtrack phase
    while len(choice_stack) > 0:
        choices = choice_stack.pop()
        slots.pop()
        used[choices[0]] -= 1

        del choices[0]
        if len(choices) == 0:
            continue

        # next choice
        choice_stack.append(choices)
        slots.append(choices[0])
        used[choices[0]] += 1
        break

# Format the results
import sys
for i in range(len(results)):
    if i%6:
        sys.stdout.write(' ')
    else:
        sys.stdout.write('\n')
    sys.stdout.write(str(results[i]))
sys.stdout.write('\n')

The output is:

102244 102424 102442 104224 104242 104422
120244 120424 120442 122044 122404 122440
124024 124042 124204 124240 124402 124420
140224 140242 140422 142024 142042 142204
142240 142402 142420 144022 144202 144220
201244 201424 201442 202144 202414 202441
204124 204142 204214 204241 204412 204421
210244 210424 210442 212044 212404 212440
214024 214042 214204 214240 214402 214420
220144 220414 220441 221044 221404 221440
224014 224041 224104 224140 224401 224410
240124 240142 240214 240241 240412 240421
241024 241042 241204 241240 241402 241420
242014 242041 242104 242140 242401 242410
244012 244021 244102 244120 244201 244210
401224 401242 401422 402124 402142 402214
402241 402412 402421 404122 404212 404221
410224 410242 410422 412024 412042 412204
412240 412402 412420 414022 414202 414220
420124 420142 420214 420241 420412 420421
421024 421042 421204 421240 421402 421420
422014 422041 422104 422140 422401 422410
424012 424021 424102 424120 424201 424210
440122 440212 440221 441022 441202 441220
442012 442021 442102 442120 442201 442210
Codie CodeMonkey
  • 7,669
  • 2
  • 29
  • 45