0

Generate a sequence of all permutation of some range of numbers のフォローアップとして、Perm クラス内に次のコードを記述しました。

/**
 * Permute A to its next permutation, if possible. Returns true if there is
 * such a permutation, and false otherwise.
 */
static boolean nextPerm(int[] A) {
    int N = A.length;
    int k = N - 1;
    int v;
    Set<Integer> S = new HashSet<Integer>();

    while (k >= 0) {
        int max = Collections.max(S);
        if (max > A[k]) {
            v = Collections.min(S);
            S.remove(v);
            S.add(A[k]);
            A[k] = v;
            int [] sArr = convertToArray(S);
            for (int i = k + 1; i < N - 1; i += 1) {
                A[i] = sArr[i - k - 1];
            }
            return true;      
        } else {
            S.add(A[k]);
            k -= 1;
        }
    }
    return false;
}

static int [] convertToArray (Set<Integer> s) {
    int [] sArr = new int[s.size()];
    int index = 0;
    for(Integer i : s) {
        sArr[index++] = i;
    }
    Arrays.sort(sArr);
    return sArr;
}

基本的に、次のように、ある範囲の数値のすべての順列のシーケンスを生成します。

Let A be a sequence of integers 0 to N-1 in ascending order 
(let's assume its an array of int[N]).    

next_permutation(A):
    k = N-1
    S = { }
    while k >= 0:
        if S contains a value larger than A[k]:
            v = the smallest member of S that is larger than A[k]
            remove v from S
            insert A[k] in S
            A[k] = v
            A[k+1:N-1] = the values in S in ascending order.
            return true
        else:
            insert A[k] in S
            k -= 1
    return false

私のコードはうまくいかないようです。誰か光を当ててくれませんか？ありがとう！

更新: 皆様からの意見を取り入れ、問題に少し取り組んだ後、問題を解決することができました! 私が学んだことがいくつかあります：

  1. Worakam が述べたように、TreeSet (HashSet と比較して) はソートされており、higher() 関数を備えているため、この質問では非常に便利です。
  2. 元々、Integer オブジェクトは完全に int ではないため、TreeSet を Integer 配列に変換するのは大変だと思っていました。ただし、(おそらく java5 の後のオートボクシング/アンボクシングが原因で)、Integer 配列内の要素を通常の int として扱い、int 項目をそれに追加することができました (for ループに示されているように)。

作業コードは次のとおりです。

static boolean nextPerm(int[] A) {
    int N = A.length;
    int k = N - 1;
    int v;
    int max = 0;

    TreeSet<Integer> S = new TreeSet<Integer>();

    while (k >= 0) {
        if (!S.isEmpty() && S.last() > A[k]) {
            v = S.higher(A[k]);
            S.remove(v);
            S.add(A[k]);
            A[k] = v;
            Integer [] sArr = new Integer[S.size()];
            S.toArray(sArr);

            for (int i = k + 1; i < N; i += 1) {
                A[i] = sArr[i - k - 1];
            }
            return true;
        } else {
            S.add(A[k]);
            k -= 1;
        }
    }
    return false;
}

みんな本当にありがとう!!

4

1 に答える 1

1

まず、セットが空のときにCollections.max(S)スローします。NoSuchElementException

第 2 に、S の最小メンバーを選択することは、「A[k] より大きい S の最小メンバー」を実装する正しい方法ではありません。

を使用する代わりに、 java.util.TreeSetHashSetなどのソートされたデータ構造を使用することをお勧めします。セットを自分でソートする必要がなくなります。そして、この方法はあなたのニーズに非常に役立つ可能性があります.higher()

于 2013-10-20T02:21:55.803 に答える