3

Java では、制限に基づいて順列を生成する方法を見つけようとしています。どうすれば順列の数を生成できますか (制限を念頭に置いて)、または少なくともその数を知ることができますか?

編集：単純な制限の定義：

可能な値:A, B, C

制限事項:a[0] == a[1]およびa[0] != [2]

データセットの例:

AABA
AABB
AABC
AACA
AACB
AACC
BBAA
BBAB
BBAC
BBCA
BBCB
BBCC
CCAA
CCAB
CCAC
CCBA
CCBB
CCBC

すべての順列を生成してから、互換性のないものを差し引いてみましたが、これは非常に非効率的です。これを効率的に行うにはどうすればよいですか？順列をカウントするだけで済みますが、それらをすべて生成するとよいでしょう。

4

3 に答える 3

2

シーケンスを生成するのではなくカウントするだけの場合は、組み合わせ論からいくつかのアイデアを借りることができます。3*3*3*3最初に、「アルファベット」{A、B、C} の 4 文字の文字列が制限なしで存在することに注意してください。最初と 2 番目の文字が同じでなければならないという制限を追加すると、3*1*3*3可能な文字列が存在します。一方、1 番目と 3 番目の文字が同じであってはならない3*3*2*3という制限を追加すると、可能性があります。

制限がプログラムへの入力の一部である場合は、これら 2 つの例を使用して、文字列内の各文字に選択肢の数を割り当てることにより、一般的な解決策を作成できます。

于 2013-03-12T01:22:34.450 に答える
2

厳密に言えば、これらは順列ではなく、有限領域上のシーケンスです。

自明なアルゴリズムは、すべてのシーケンスを生成し、制限を満たすシーケンスのみを出力することです。ドメイン A で長さ n のすべてのシーケンスを生成することは、再帰を使用すると非常に簡単です。

class SequenceGenerator {
    char[] domain;
    char[] sequence;
    int n;

    void generate(int i) {
        if (i == n) {
            System.out.println(new String(sequence));
        } else {
            for (char c : domain) {
                sequence[i] = c;
                generate(i + 1);
            }
        }
    }
}

より洗練されたアルゴリズムは、部分的に形成されたシーケンスをチェックします。たとえば、シーケンスが AB で始まることがわかっている場合、それが制限シーケンス [0] == シーケンス [1] を満たさないことはすでにわかっているため、残りの要素を埋める意味はありません。

abstract class PickySequenceGenerator extends SequenceGenerator {

    @Override
    void generate(int i) {
        if (possible(i)) {
            super.generate(i);
        }
    }

    /** @return whether a sequence starting with the first i elements of {@link #sequence} can still satisfy all constraints */
    abstract boolean possible(int i);
}

効率をさらに高めるために、最も制約のあるシーケンス要素に最初に値を割り当てることができます。

于 2013-03-12T01:12:46.737 に答える
0 
for (char a0='A'; a0<='C'; a0++) {
  char a1=a0;
  for (char a2='A'; a2<='C'; a2++) {
    if (a0 != a2) {
      for (char a3='A'; a3<='C'; a3++) {
         a.append(a0 + a1 + a2 + a3);
      }
    }
  }
}

（疑似コードですが、画像が得られると思います）

于 2013-03-12T00:38:40.563 に答える