3

理解できないように見えるインタビューの質問を受けました:整数の配列が与えられました。配列内の数値のすべての順列を出力するプログラムを作成します。出力は降順でソートする必要があります。たとえば、配列 { 12, 4, 66, 8, 9} の場合、出力は次のようになります。

9866412

9866124

9846612

....

....

1246689

明らかな解決策の 1 つは、並べ替えてから並べ替えることですが、それには 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 に答える