2

给出了以下算法，我们应该用java写出来。但是，当我尝试逐行理解时，会感到困惑，尤其是以下部分：

A[k+1:N-1] = S 中的值升序排列

据我了解，该套装在任何时候都只有 1 个号码。A[k+1:N-1]当集合只有 1 个数字时，我们如何替换？

0让 A 是一个按升序排列的整数序列N-1（假设它是一个 的数组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
4

1 回答 1

1

显示的算法类似于按字典顺序生成的算法。您可以阅读文章以获取更多信息。

@templatetypedef 关于如何按升序将数组中的项目替换为一组值的任何线索？例如 A[k+1:N-1] = S 中的值按升序排列。我应该使用 toArray() 吗？

这不是必需的。您可以尝试始终保持 S 数组排序。每次您想在数组中插入一个新数字时，都将其插入其中，这样数组就可以保持排序。例如，如果您S = [5 7 8]到目前为止并且想要插入6，则插入 5 到 7 - 之间S = [5 6 7 8]。这样，替换步骤只是将元素从 S 复制到 A[k+1:N-1]。

于 2013-11-15T08:40:31.597 回答