Java で反復アプローチを使用して配列のすべての順列を効率的に生成するにはどうすればよいですか?

置換アルゴリズム

配列のすべての置換を生成するには、現在の配列から昇順で開始する反復アプローチを検討してください。目標は、降順パターンを破る要素を交換することによって、降順に徐々に変換することです。長さ - 1; 尾部 --) {

}`

実装

if (ind[tail - 1] < ind[tail]) { // still increasing

    // find last element that does not exceed ind[tail - 1]
    int s = ind.length - 1;
    while (ind[tail - 1] >= ind[s])
        s--;

    swap(ind, tail - 1, s);

    // reverse order of elements in the tail
    for (int i = tail, j = ind.length - 1; i < j; i++, j--)
        swap(ind, i, j);
    break;
}

個別と反復の両方を処理する Java での実装例を次に示します。要素:

例

配列 [3, 4, 6, 2, 1] の場合、順列は次のとおりです:

import java.util.Arrays;
import java.util.Iterator;
import java.lang.reflect.Array;

class Permutations<E> implements Iterator<E[]> {

    private E[] arr;
    private int[] ind;
    private boolean has_next;

    public E[] output; // next() returns this array

    Permutations(E[] arr) {
        this.arr = arr.clone();
        ind = new int[arr.length];

        // convert an array of any elements into an array of integers
        Map<E, Integer> hm = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            Integer n = hm.get(arr[i]);
            if (n == null) {
                hm.put(arr[i], i);
                n = i;
            }
            ind[i] = n.intValue();
        }
        Arrays.sort(ind); // start with ascending sequence of integers

        output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length);
        has_next = true;
    }

    public boolean hasNext() {
        return has_next;
    }

    public E[] next() {
        if (!has_next) {
            throw new NoSuchElementException();
        }

        for (int i = 0; i < ind.length; i++) {
            output[i] = arr[ind[i]];
        }

        // get next permutation
        has_next = false;
        for (int tail = ind.length - 1; tail > 0; tail--) {
            if (ind[tail - 1] < ind[tail]) { // still increasing

                // find last element that does not exceed ind[tail - 1]
                int s = ind.length - 1;
                while (ind[tail - 1] >= ind[s]) {
                    s--;
                }

                swap(ind, tail - 1, s);

                // reverse order of elements in the tail
                for (int i = tail, j = ind.length - 1; i < j; i++, j--) {
                    swap(ind, i, j);
                }

                has_next = true;
                break;
            }
        }

        return output;
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public void remove() {
        // not supported
    }
}

以上がJava で反復アプローチを使用して配列のすべての順列を効率的に生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。