java - ランダムな順序を生成しますが、Javaで制約があります

Question

整数リストを配置するとき、別のランダムな順序を制約付きで生成するにはどうすればよいですか?

たとえば、整数 1、2、3、4 をコレクションに入れ、「1 2 3 4」、「1 2 4 3」、「1 3 2 4」、「2 1 3」のような結果を出力しようとすると、 4"、または "2 1 4 3" (1 は 3 の前に、2 は 4 の前になければなりません)

前もって感謝します

Answer 1

考慮できることの1つは、要素をランダムに交換することです。コレクション内のランダムな位置を選択し、その位置にある要素を次の要素と交換することができます。このようにして、1を3に、または2を4に交換するのを防ぐことができます。番号が適切にスクランブルされるまで、これを繰り返し行うことができます。

[1, 2, 3, 4]乱数は0で、位置1の要素と交換します。

[2, 1, 3, 4]乱数は1で、位置2の要素と交換します。

要素は1と3なので、交換しないでください。

[2, 1, 3, 4]乱数は2で、位置3の要素と交換します。

[2, 1, 4, 3]等

制約を一般化したい場合は、条件を変更するだけです。要素が1と3、または2と4のいずれかである場合に交換を拒否する代わりに（上記の例のように）、交換する位置にある2つの要素が互いに2以内にないことを確認できます。if(b==a+2)continue;：

要素は5と7なので、交換しないでください。

if(7==5+2)continue; // ie don't swap.

Answer 2

文字列として使用する場合は、この回答のアルゴリズムを使用してすべての数値を交換できます

すべての数値を入力したら、それらを連結します。それらを数字や文字列として扱う必要はありません。あなたがしたいのはそれらを並べ替えることです。

結果が得られたら、制約が一致するかどうかを確認してから、別のリストを印刷できます。おそらくこのようなもの

private boolean isConstraintSatisfied(String wholeString, String firstNum, String secondNum){
    return wholeString.indexOf(firstNum) <= wholeString.indexOf(secondNum);
}

最もエレガントな解決策ではありませんが、うまくいくと思います。入力セットが小さい場合は、非効率的すぎないようにする必要があります。

Answer 3

ここで定義したものは、半順序として知られています。半順序を満たすランダムな順列、つまりランダムな線形拡張を生成したいと考えています。

幸いなことに、Java API は を指定Collections.shuffleしており、これはランダム順列を生成するための Fisher-Yates アルゴリズムを実装しています。残念ながら、標準の Java 手法 viaCollections.sortは比較ソートであるため、必要な部分順序とは異なり、合計順序に重点が置かれています。実際、Java API には、ここで使用できるソート アルゴリズムがありません。

「転置による Poset の線形拡張の生成」で説明されている1 つのアプローチには、Hassan のソリューションと同様の方法でセット内の隣接する要素を交換することが含まれます。これは、当面の局所化された問題に対して機能する方法のようです。