4

Python では、アイデアをいじっていますが、それを正しく実装する方法が正確にはわかりません。

26 文字 ('A' - 'Z') のプールがあり、各文字は必要に応じて何度でも使用できます。これらの文字を使用してリストを作成したい。各リストは 10 文字の長さで、内部に繰り返しはありません。生成された 2 つのリストを比較すると、共通する文字が1 つだけあることを保証したいと思います。

質問:

  • これを行う簡単な方法 (つまり、ライブラリ関数を使用する方法) はありますか?
  • プールのサイズ (pool_size) とリストの長さ (list_length) から、作成できるリストの最大数を計算できますか?

関連資料へのポインタをいただければ幸いです。アルキメデスのレバーを置く場所ほど実装は必要ありません (次のように読まれます: アイデアを構築する前に基盤が必要です)。

「私に立つ場所をください。地球を動かします。」- アルキメデス

更新: アルファベットで作業するのに十分であると考えるのは、どれほど素朴なことでしょうか。プールを 300 シンボルに拡張してみましょう。ただし、リストの長さは 10 のままにします。うまくいきますか?

4

2 に答える 2

6

選択できるのは 26 文字のみで、生成できるリストは 2 つだけです。

無作為に 1 つの文字を選択し、両方のリストに入れます。次に、さらに 18 個の異なる文字を選び、各リストにランダムに 9 個入れます。次に、リストは次のようになります。

ABCDEFGHIJ
AKLMNOPQRS

3 番目のリストを追加すると、未使用の文字が 7 文字しかないため、制約を満たすことができなくなります。3 番目のリストは、他のリストの 1 つと少なくとも 2 文字を共有する必要がありますが、これは許可しません。

アップデート

これはあなたの更新された質問に部分的にしか答えていませんが、あなたや他の人が最適な解決策を見つけるのに役立つかもしれないので、とにかく投稿します.

一般に、nシンボルと長さのリストを使用すると、上記のアルゴリズムを使用してx少なくともfloor((n-1)/(x-1))リストを簡単に生成できます (1 文字を選択し、それをすべてのリストに追加します。300 個のシンボルと長さ 10 のリストの場合、33 個のリストが得られます)。

しかし、別のアルゴリズムを使用することで、これを改善することができます。たとえば、n が 10 で x が 4 の場合、上記のアルゴリズムは 3 つのリストのみを返します。

ABCD
AEFG
AHIJ

しかし、文字をより効率的に再利用するアルゴリズムは、5 つのリストを生成できます。

ABCD
AEFG
BEHI
CFHJ
DGIJ

私は貪欲なアルゴリズムを使用してこれらのリストを生成しました。新しいリストごとに、以前のリストからできるだけ多くの異なる文字を再利用します。つまり、新しい文字をできるだけ少なく追加します。

2 番目のリストは、最初のリストから 1 文字を再利用し、3 つの新しい文字を追加します。3 番目のリストは、最初の 2 つのリストのそれぞれから別の文字を再利用するため、新しい文字を 2 つだけ導入します。4 番目のリストは、以前に使用された 3 つの文字を再利用し、さらに 1 つの新しい文字を追加します。最終的なリストでは、以前の各リストの文字を再利用できるようになり、新しい文字を追加する必要がなくなりました。

更新 2

貪欲なアルゴリズムは間違いなく最適なソリューションではありません。

試してみましょう: n = 26, x = 2

簡単な解決策は、最適な 25 個のリストを提供します。

AB
AC
AD
..
AZ

ただし、貪欲なアルゴリズムは 3 つのリストのみを生成します。

AB
AC
BC

現在、ルールの 1 つを破ることなく、これ以上リストを追加することはできません。

于 2012-10-24T18:54:08.540 に答える
1

これは、Set と Line Length のすべての値に対して私が見つけた一般的な解決策です。1 つ目は、2 つのソリューションが同じ共通要素を共有することは望まないが、各ソリューションには他のすべてのソリューションと共通の要素が 1 つあることを前提としています。フォームを選択する無限のプールがある場合、ソリューションの総数は各ソリューションの長さによって制限されます。

SET_LENGTH = 10
CHOICE_LENGTH = 300

data = set(range(CHOICE_LENGTH))
solutions =[]
solution_sets = []
used = set()

while True:
    new_solution = []
    #Try to get unique values from each previous set
    try:
        for sol_set in solution_sets:
            while True:
                candidate = sol_set.pop()
                if not candidate in used:
                    new_solution.append(candidate)
                    used.update([candidate])
                    break
    except KeyError, e:
        print e
        break
    #Fill with new data until the line is long enough
    try:
        while len(new_solution) < SET_LENGTH:
            new_solution.append(data.pop())
    except KeyError, e:
        print e
        break
    solutions.append(new_solution)
    solution_sets.append(set(new_solution))
#Show the results
for solution in solutions:
    print solution
print "Orphans %s" % len(data)

たとえば、n = 300 x = 10 の場合:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[1, 10, 19, 20, 21, 22, 23, 24, 25, 26]
[2, 11, 19, 27, 28, 29, 30, 31, 32, 33]
[3, 12, 20, 32, 34, 35, 36, 37, 38, 39]
[4, 13, 21, 33, 34, 40, 41, 42, 43, 44]
[5, 14, 22, 27, 36, 40, 45, 46, 47, 48]
[6, 15, 23, 28, 37, 41, 45, 49, 50, 51]
[7, 16, 24, 29, 38, 42, 47, 49, 52, 53]
[8, 17, 25, 30, 39, 43, 48, 50, 52, 54]
[9, 18, 26, 31, 35, 44, 46, 51, 53, 54]
Orphans 245

同じ共通要素を共有するソリューションの数が気にならない場合は、さらに簡単です。

SET_LENGTH = 2
CHOICE_LENGTH = 300

data = set(range(CHOICE_LENGTH))
solutions =[]
alpha = data.pop()
while True:
    new_solution = [alpha]
    try:
        [new_solution.append(data.pop()) for x in range(SET_LENGTH-1)]
    except KeyError, e:
        break
    solutions.append(new_solution)

for solution in solutions:
    print solution
print "Solutions: %s" % len(solutions)
print "Orphans: %s" % len(data)
于 2012-10-24T20:42:55.157 に答える