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 相比）在这个问题中非常方便，因为它已排序并具有更高的（）函数。
  2. 最初我认为将 TreeSet 转换为 Integer 数组会很忙，因为 Integer 对象不是很 int。然而，事实证明（可能是由于 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

其次，选择 S 的最小成员并不是实现“S 中大于 A[k] 的最小成员”的正确方法。

我建议HashSet您不要使用 a ，而应使用排序的数据结构，例如java.util.TreeSet。它将消除您自己对集合进行排序的需要。该方法higher()可能对您的需要非常有用。

于 2013-10-20T02:21:55.803 回答