8

たとえば、7人の家族がいるとしましょう。

["John", "James", "Jenna", "Joseph", "Jane", "Jacob", "Joanne"]

彼らは皆、クリスマスプレゼントのシーズンに向けて準備をしています。彼らは、すべてがスムーズに機能することを確認するためのいくつかのルールに同意しました。

  • 誰もが1つの贈り物をしなければなりません。
  • 誰もが1つの贈り物を受け取らなければなりません。
  • 誰も自分に贈り物をすることはできません。
  • 誰も彼の配偶者に贈り物をすることはできません。（ジェーンとジョンは配偶者です）
  • 彼が去年与えたのと同じ人に誰も与えることはできません。（昨年、ジョンはジェームズに、ジェームズはジェナに、ジェナはジョセフに、ジョセフはジェーンに、ジェーンはジェイコブに、ジェイコブはジョアンに、ジョアンはジョンに与えました）
  • 最後に、2人がお互いに贈り物をすることはできません。たとえば、ジョンがジェナに寄付している場合、ジェナはジョンに寄付しない場合があります。

ルールは複雑であるため、これらのルールを守りながら、誰が誰に誰に与えることができるかを理解するのは困難でした。その結果、彼らは私を雇って、人々がお互いに与えることができるすべての可能な法的方法を表示するプログラムを書くようになりました。

この問題をエレガントに解決するためにどのアルゴリズムを使用できますか？

4

2 に答える 2

4

単純なバックトラッキングアルゴリズムを使用します。Pythonジェネレーター関数の使用：

def calc_gifts(names, blacklist, gifts={}):
    if len(names) > 0:
        name, rest = names[0], names[1:]
        for other in names + list(gifts):
            if (other != name and 
                    other not in blacklist[name] and
                    (other not in gifts or gifts[other] != name) and
                    other not in gifts.values()):

                gifts_new = dict(gifts.items() + [(name, other)])
                for solution in calc_gifts(rest, blacklist, gifts_new):
                    yield solution
    else:
        yield gifts

ここで、名前とブラックリストを設定し、ジェネレーターにソリューションを生成させます。

all_names = ["john", "james", "jenna", "joseph", "jane", "jacob", "joanne"]
blacklist = {"john":   ["james", "jane"],
             "james":  ["jenna"],
             "jenna":  ["joseph"],
             "joseph": ["jane"],
             "jane":   ["jacob", "john"],
             "jacob":  ["joanne"],
             "joanne": ["john"]}
generator = calc_gifts(all_names, blacklist)
solution = next(generator)

solution次にdict、贈答者と受取人の{'joanne': 'joseph', 'james': 'john', 'jane': 'joanne', 'joseph': 'jacob', 'jacob': 'jane', 'john': 'jenna', 'jenna': 'james'}です。

最初の解決策、つまりを使用するnext(generator)場合は、 calc_gifts10回だけ呼び出されます。224のソリューションすべてについて、たとえば、list(generator)それを使用すると、約 1000回。

于 2012-10-30T10:52:31.273 に答える
1

7x7 のグリッドで開始し、行と列にそれぞれの人がいて、行に記載されている人が列に記載されている人に贈り物をすることが許可されているかどうかを示しているとしたらどうなるでしょうか。

最初に、すべての組み合わせを許可されているものとしてマークし、次に、制約 3、4、および 5 によって明示的に許可されていないものを削除し始めます。ギフトの有効な組み合わせはすべて、この時点で残したもののサブセットである必要があります。これが開始位置になります。

今、あなたは決断を下さなければなりません。すべての決断は、あなたが残した可能性に影響を与えます。一部の決定が間違っていることが判明する可能性があり、最終的に誰もが贈り物を受け取るわけではありません. その場合、その決定を取り消して別の方法を試す必要があります (ヒント: これには再帰を使用してください)。

構造化された方法ですべての可能性を試すと、すべての解決策が存在する場合に必ず見つかります。

今、それを彼らのお金の価値にしてください:)

于 2012-10-26T16:43:33.970 に答える