给定n，生成所有大小小于0.5n的排列

Question

给定n，生成所有大小小于0.5n的排列

arraysalgorithmoptimizationjuliapermutation

3

给定一个整数 n，我希望以尽可能高效的方式生成一个向量，其中包含小于或等于 0.5n 大小的所有整数的排列。

例如，对于 n=7，这将是：

15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [1, 3]
 [2, 1]
 [2, 3]
 [3, 1]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]

我目前的想法是生成所有大小小于0.5n的k排列，然后将它们附加在一起：

using Combinatorics

function generate_half_perm(n)
    half_n = floor(Int, n/2)
    result = []
    for l in 1:half_n
            for c in permutations(1:half_n, l)
                    push!(result, c)
            end
    end
    return result
end

调用generate_half_perm(7)可得到此帖子的第一个实例。我认为这段代码的复杂度目前高于没有生成组合所需的代码的复杂度O(2^(n/2).n)，即combinations(1:half_n, l)。

我想知道是否有更好的想法可以得到更快的代码，考虑到我的 n 可能会超过100。

我曾想过使用这个代码 [Julia中计算排列的最佳方法]，但是produce函数已弃用，应根据其他答案 [如何用通道替换consume和produce]进行替换，现在对我来说变得更加复杂！

如果您有更好的算法思路，不涉及Julia的实现，我很乐意尝试 :)

小修改：我意识到我想要的是：

collect(Iterators.flatten(permutations.(powerset(1:7,0, floor(Int, 7/2)))))

感谢@Przemyslaw Szufel让我找到它 :)

- JKHA

当n=100时，这些数字的数量太多了，远远超出了地球上所有内存的存储容量。如果n=100，则有大约3e64个大小为n/2的数字。 - dmuir

@dmuir，是的，你说得对！我会尽可能地运行我的项目，但永远不会达到100 :) - JKHA

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Przemyslaw Szufel · Accepted Answer

对于您所说的值“N的一半”等于3，应该是这样的：

using Combinatorics
Iterators.flatten(permutations.(powerset(1:3,1)))

请注意，这是不分配内存的，如果您想查看结果，则需要使用collect。

julia> collect(Iterators.flatten(permutations.(powerset(1:3,1))))
15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [2, 1]
 [1, 3]
 [3, 1]
 [2, 3]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]