3

我有一个我似乎无法弄清楚的面试问题：给定一系列整数。编写一个程序来打印数组中数字的所有排列。输出应按降序排序。例如对于数组 { 12, 4, 66, 8, 9}，输出应该是：

9866412

9866124

9846612

……

……

1246689

一个明显的解决方案是先排列然后排序，但这需要 n！记忆。我正在寻找需要多项式记忆的东西。

我尝试编写递归解决方案，该解决方案涉及从最大的字典序数开始生成排列：

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)

但这对于以下情况失败：

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

1 回答 1

2

看来这可以通过按顺序生成数字排列而不重复，然后为每个数字排列找到所有匹配值来解决。这是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])

输出：

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

但是，在某些情况下，这可能效率极低。

于 2012-09-03T17:41:41.590 回答