1

この質問は、私が書き込もうとしている、物理的なパーツのチェーンを接続するプログラムに関するものです。私はそれを質問の最も単純な形に蒸留したと思います。また、この問題を説明する追加の単語を誰かが知っていれば幸いです。関連する質問を検索してから約30分でも、この問題の名前が見つからなかったからです。

N個のベクトルがあります。各ベクトルから1つの値を選択し、繰り返しを許可しない場合、私が見つけようとしているタイプの1つの順列があります。ブルートフォースなしでそれらすべてを見つけるための擬似コードアルゴリズムとは何ですか？

例：
あなたはベクトルを持っています

v1=[1 2]   v2=[1 2 3]   v3=[1 2 3 4]

（注を編集：ベクトルのネストは意図的ではなく、アルゴリズムで利用することはできません。）各ベクトルから値を選択し、繰り返しを許可しません。

Value 1 is from v1 ---> 2
Value 2 is from v2 ---> 1   
Value 3 is from v3 ---> 4

Resulting permutation is [2 1 4].

これは許容される順列の1つです。これは、繰り返されるために許可されない順列の例です。

Value 1 is from v1 ---> 2
Value 2 is from v2 ---> 1
Value 3 is from v3 ---> 2    

Resulting permutation is [2 1 2], which is invalid due to repeats.

すべての有効な順列を見つけるためのアルゴリズムは何ですか？

それらを計算する前に、いくつの順列があるかを計算できる場合のボーナスポイント。

誰よりも早く答えを思いつくことができれば、必ず投稿します。

4

2 に答える 2

4

与えた例にはネストされたベクトルがあります。つまり、のエントリはのエントリv_iのサブセットですv_{i+1}。これが実際にアプリケーションの一般的なケースである場合、ソリューションの数は単純に次のようになります。

n_1 * (n_2 - 1) * ... * (n_k - (k-1))

ここで、n_iはの長さでv_iあり、kネストされたベクトルがあります。

アルゴリズムに関する限り、考えられるすべてのソリューションを生成したい場合は、すでに選択されているエントリを削除した後、連続する各ベクトルから選択するよりも良い方法はわかりません。

ネストされていない場合、この問題を視覚化する良い方法は、次の意味での結婚問題としてです。与えられたベクトルkに対応する頂点を作成しますk

v_1  v_2 ...  v_k

m結合されたベクトルの個別のエントリに対応する別の頂点

a_1 a_2 ... a_m

次に、にが表示されている場合にのみに接続a_iします。目標は、すべての'に接触するsとsの間の最大一致を見つけることです。つまり、それぞれが正確に1つのエッジの端点になるようにエッジを選択します。v_ja_iv_jvavkv_i

拡張パスを使用するなど、標準的なアルゴリズムはいずれも、1つのソリューションを見つけるか、すべてを生成するために機能します。

于 2012-09-11T05:05:42.240 に答える
1

この問題は段階的に解決できると思います。s1、s2、s3、..、skをv1、v2、..、vnを含む解とします。ここで、現在のすべてのソリューションsiと要素j（vn + 1のj）に対してvn + 1を使用して、jがすでにsiにあるかどうかを確認します。ない場合は、新しいコレクション（n + 1に対応）に追加します。

  1. S={{j}をv1のjに対して初期化します}
  2. n = 2..mの場合：
    1. newS = {}
    2. vnのjの場合
      1. Sのsの場合
        1. jがsにない場合は、sU{j}をnewSS=newSに追加します。
  3. 戻り値
于 2012-09-11T05:07:31.797 に答える