6

基本的に、いくつかの小さな行列が別の大きな行列に適合するかどうかをテストする複雑な計算アルゴリズムがあります。
すべてが大きな行列に収まるかどうかは、小さな行列の順序によって異なります。小さな行列が適合しない場合は、ArrayListを再配置し、すべての可能な順序/シーケンスがテストされるまで再試行する必要があります。

私が5つの小さな行列を持っている場合、合計で5つになります。（= 120）配列が持つことができる可能な順序。

私の問題は、これらのオブジェクト（行列）を再配置する方法がわからないため、考えられるすべての順序をテストできることです。誰かが私を助けてくれることを願っていますか？

4

2 に答える 2

13

nオブジェクトには順列n!があります。セットを考えてみましょう：

S = {a1, a2, a3 ..., an};

上記のセットの順列を見つけるためのアルゴリズムは次のとおりです。

foreach(item i : S) {
   /* all other item except i1 and i */
   foreach(item i1 : S - {i}) {
       foreach(item i2 : S - {i, i1}) {
          .
          .
          .
          foreach(item in : S - {i, i2, .... in-1}) {
             /* permutation list */
             P = { i1, i2, ...., in-1, in }; 
          }
       }
   }
}

明らかにループを持つことはできませんが、リストに要素n forを取得するまでこのアルゴリズムを再帰的に構築できます。以下は、上記のアルゴリズムを使用して順列を実行する実際のJavaコードです。nP

public static void 
permutations(Set<Integer> items, Stack<Integer> permutation, int size) {

    /* permutation stack has become equal to size that we require */
    if(permutation.size() == size) {
        /* print the permutation */
        System.out.println(Arrays.toString(permutation.toArray(new Integer[0])));
    }

    /* items available for permutation */
    Integer[] availableItems = items.toArray(new Integer[0]);
    for(Integer i : availableItems) {
        /* add current item */
        permutation.push(i);

        /* remove item from available item set */
        items.remove(i);

        /* pass it on for next permutation */
        permutations(items, permutation, size);

        /* pop and put the removed item back */
        items.add(permutation.pop());
    }
}

主な方法は次のとおりです。

public static void main(String[] args) {
    // TODO Auto-generated method stub


    Set<Integer> s = new HashSet<Integer>();
    s.add(1);
    s.add(2);
    s.add(3);

    permutations(s, new Stack<Integer>(), s.size());
}

結果を出力しました：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
于 2013-01-03T05:24:42.560 に答える
0

Java> 8を使用している場合は、非常に賢いソリューションがあります。

static Stream<List<Integer>> permutations(List<Integer> input) {
    if (input.size() == 1) {
        return Stream.of(new LinkedList<>(input));
    }
    return input.stream()
            .flatMap(first -> permutations(input.stream()
               .filter(a -> !a.equals(first))
               .toList())
            .map(LinkedList::new)
            .peek(l -> l.addFirst(first)));
}
于 2021-12-29T20:05:13.897 に答える