3

アイテムの順序が保持され、結果のリストが 1 つの整数に連結された場合に可能な限り小さくなるように、整数の 2 つのリストからアイテムを結合する方法がわかりません。

この質問に似ている可能性がありますが、与えられた答えは私のサイズの制約に対応していません: Interleave different length lists, elimating duplicates and preserve order in Python

たとえば、次のようになります。

a = [3,4,5,7,9,2]
b = [3,5,7,4,2,8]

これら 2 つのリストの最短の組み合わせは次のようになります。

c = [3,4,5,7,4,9,2,8]

連結された整数値 34574928 を使用

数値の順序がリストの長さに影響しないが、連結された整数のサイズに影響する場合があります。上記の例では、項目の順序を維持しながら 4 と 9 を入れ替えることができますが、最終的な数字は必要以上に大きくなります。

さらに明確にするために：

最終的なリストには、元の 2 つのリストからの各数字のすべてのインスタンスが含まれている必要があります。上記の例で 2 つの組み合わせをより適切に表すには、次のようにします。

a = [3,4,5,7,  9,2  ]
b = [3,  5,7,4,  2,8]
c = [3,4,5,7,4,9,2,8]

もちろん、いつもきれいにうまくいくとは限りません。この場合、2 つのリストの 4 つの数字 (3、5、7、および 2) を完全にマージできます。4 つの数字 (4、4、9、および 8) は、より大きなリストを作成しないと結合できませんでした。例えば：

a =     [3,    4,5,7,  9,2]
b =     [3,5,7,4,  2,8    ]
bad_c = [3,5,7,4,9,2,8,9,2]

この場合、3 と 4 のうちの 1 つだけを組み合わせました。これら 2 つの結果例の項目を連結すると、次のようになります。

c =     34574928
bad_c = 357492892

どちらも順序付け要件を満たしていますが、順序付け要件を満たしているが、整数に連結したときに bad_c よりも小さい別の結果があるため、bad_c は正しくない結果です。

4

2 に答える 2

1

これがうまくいくと思う簡単なアルゴリズムです。実装はかなり簡単なので、投稿しません。

1. リストについては、最初の共通要素を見つけ、2 つのリストが a & b であると言う前に要素を収集します。

2.a. 共通する要素がない場合は、最初の要素を比較してマージし、次に小さい方のリストのインデックスをインクリメントして比較します。あなたはアイデアを得ました！

2. b. 次に、一般性を失うことなく、a[3] は b[4] に一致し、a[0]-a[2] と b[0]-b[3] を収集し、ケースを使用して 7 つのアイテムをマージします。共通の要素がなく、最後に a[3] の値を追加します。

3. 同様に、リストの最後までこれを行います。最後に追加されたアイテムの後に、残りのアイテムをマージします。

4. このために、マージされるサブリストの両方のリストから開始インデックスと終了インデックスを取得する関数を記述できます。

このソリューションが機能することを願っています。正しいように見えますが、まだ試していません。私が何かを見逃した場合は、それを指摘してください。

于 2014-06-03T18:27:50.640 に答える
1

これは、再帰を使用したかなり長いが正しい（質問の議論からわかる限り）実装です。

重要なポイント:

  • を使用して両方のリストを反復処理します.pop(index)。これにより、再帰を使用できます。関数が再帰するにつれて両方のリストがどんどん小さくなり、一方のリストがlen(0).
  • 番号はどちらのリストからでも選択でき、1 つのリストから連続して選択できる番号に制限はありません。
  • 連続した重複は許可されません。
  • 等しくない 2 つの数字を比較する場合、常に小さい方の数字が大きい方に配置されます。23xxx は常に 32xxx よりも低くなります。

基本的に、次のようなものがある場合[1,2,3]、[6,0,4]最初のリストのすべての数字は 2 番目のリストの最初の数字の前になります。 x に選択された値。

z = [None]
#set to None so that z[-1] doesn't throw an out-of-range error

def small_list(a,b): #recursive function

    ### BASE CASE ###

    if len(a) == 0: #if one list empty, can only add rest of other list
        for i in b:
            if i != z[-1]: #account for duplicates
                z.append(i)
            # else: #don't add duplicates

        return z.pop(0) #end recursion, remove extraneous None

    elif len(b) == 0: #if one list empty, can only add rest of other list
        for j in a:
            if j != z[-1]:#account for duplicates
                z.append(j)
            # else: #don't add duplicates

        return z.pop(0) #end recursion, remove extraneous None

    #Otherwise, we need to check whichever is smaller.  
    #The smaller number should ALWAYS go in the larger place (tens,hundreds,etc.) to make a smaller number.

    ### RECURSIVE CASE ###

    if a[0] < b[0]:
        if a[0] != z[-1]:
            z.append(a.pop(0))
        else:
            a.pop(0)
    elif a[0] > b[0]:
        if b[0] != z[-1]:
            z.append(b.pop(0))
        else:
            b.pop(0)
    elif a[0] == b[0]:
        a.pop(0)

    small_list(a,b) # recur

例:

z = [None]

l1 = [1,2,3,2]
l2 = [2,1,1,1]

small_list(l1,l2)
print z

この最初の例[1, 2, 1, 3, 2]は、現在正しいものを出力します。

z = [None]

l1 = [1,2,3]
l2 = [4,5,6]

small_list(l1,l2)
print z

この 2 番目の例は、これも正しく出力さ[1, 2, 3, 4, 5, 6]れます。

上記の例を計算する方法の流れは次のとおりです。

# The format is: [final list]  len(a)  [list a]  len(b)  [list b]

[] len(a) = 6 [3, 4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# 3 repeated, so remove it.
[] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 3), and remove from corresponding list
[3] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 5), and remove from corresponding list
[3, 4] len(a) = 4 [5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# 5 repeated, so remove it.
[3, 4] len(a) = 3 [7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (7 v 5), and remove from corresponding list
[3, 4, 5] len(a) = 3 [7, 9, 2] len(b) = 4 [7, 4, 2, 8]
# 7 repeated, so remove it.
[3, 4, 5] len(a) = 2 [9, 2] len(b) = 4 [7, 4, 2, 8]
# add lower of first two indices to final (9 v 7), and remove from corresponding list
[3, 4, 5, 7] len(a) = 2 [9, 2] len(b) = 3 [4, 2, 8]
# add lower of first two indices to final (9 v 4), and remove from corresponding list
[3, 4, 5, 7, 4] len(a) = 2 [9, 2] len(b) = 2 [2, 8]
# add lower of first two indices to final (9 v 2), and remove from corresponding list
[3, 4, 5, 7, 4, 2] len(a) = 2 [9, 2] len(b) = 1 [8]
# add lower of first two indices to final (9 v 8), and remove from corresponding list
[3, 4, 5, 7, 4, 2, 8] len(a) = 2 [9, 2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)
[3, 4, 5, 7, 4, 2, 8, 9] len(a) = 1 [2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)

#Finally:
[3, 4, 5, 7, 4, 2, 8, 9, 2]
于 2014-04-18T20:12:36.287 に答える