generate all permutations in order without using excessive memory

Question

I got an interview question that I can't seem to figure out: Given an array of intergers. Write a program to print all the permutations of the numbers in the array. The output should be sorted in a decreasing order. For example for the array { 12, 4, 66, 8, 9}, the output should be:

9866412

9866124

9846612

....

....

1246689

One obvious solution is to permute then sort but that will take n! memory. I'm looking for something that will take polynomial memory.

I tried writing recursive solution that involved generating the permutations starting from the largest lexicographical numbers:

def compare(x,y):
    for i in range(max(len(x), len(y))):
        if len(x) <= i:
            return compare(x[0], y[i])
        elif len(y) <= i:
            return compare(x[i], y[0])
        elif x[i] < y[i]:
            return -1
        elif x[i] > y[i]:
            return 1
    return 0

def print_all_permutations(so_far, num_lst):
    if not num_lst:
        print so_far
    for i in range(len(num_lst)):
        cur = num_lst.pop(i)
        print_all_permutations(so_far + [str(cur)], num_lst)
        num_lst.insert(i, cur)

input_arr = sorted([str(x) for x in [3,31,0]], cmp = compare, reverse=True)

But this fails for cases like:

['3', '31', '0']
3310
3031
error 3130(['31', '3', '0']) is greater than ['3', '0', '31'](3031)
3130
3103
331
313

Answer 1

It appears this can be solved by generating the permutations of the digits in order without duplicates, and then for each permuation of digits finding all the matching values. Here's an example in python:

def reversed_numerically_ordered_permutations(values):
  def permute(digits,prefix):
    assert type(digits) is str
    if len(digits)==0:
      match(prefix,values,[])
    last_digit=None
    for i in range(len(digits)):
      if digits[i]!=last_digit:
        permute(digits[0:i]+digits[i+1:],prefix+digits[i])
        last_digit=digits[i]

  def match(x,values,prefix):
    assert type(x) is str
    if len(x)==0 and len(values)==0:
      print prefix
    for i in range(len(values)):
      value=values[i]
      value_str=str(value)
      if x.startswith(value_str):
        match(x[len(value_str):],values[0:i]+values[i+1:],prefix+[value])

  digits=sorted(''.join(str(x) for x in values),reverse=True)
  digits=''.join(digits)
  permute(digits,'')

reversed_numerically_ordered_permutations([3,31,0])

Output:

[3, 31, 0]
[31, 3, 0]
[31, 0, 3]
[3, 0, 31]
[0, 3, 31]
[0, 31, 3]

However, this could be extremely inefficient in some cases.