有/无替换的排列和组合，用于不同/不明显的项目/多集 [英] Permutations and combinations with/without replacement and for distinct/non-distinct items/multiset
问题描述
在此主题中，我试图在此处包括所有常见问题及其答案.我希望这对某人有用.
In this thread, I am trying to include all the commonly asked questions and their answers here. I hope this will be useful for someone.
常见问题:如何从n个对象生成r个对象的序列?
General question: How to generate sequences of r objects from n objects?
- 组合与排列.
- 可以更换与不可以更换
- 不同项目对比非不同项目(多集).
总共有2^3=8个此类问题.
[更新]
Josh O'Brien建议这8个问题与十二折方式有关.确实，区别性"问题以十二种方式包括在内，而非区别性"问题不包括在内.无论如何，将这8个问题与十二重方式进行比较很有趣.请参阅评论以进一步阅读.
Josh O'Brien suggests that the 8 questions are related to twelvefold way. Indeed, the "distinct" questions are included in twelvefold way, while the "non-distinct" questions are not included. Anyway, it is interesting to compare the 8 questions here with twelvefold way. See the comments for further readings.
推荐答案
EDIT: I have updated the answer to use a more efficient package arrangements
布置包含一些有效的生成器和迭代器，用于排列和组合.已经证明arrangements优于大多数现有的同类包装.可以在此处找到一些基准.
arrangements contains some efficient generators and iterators for permutations and combinations. It has been demonstrated that arrangements outperforms most of the existing packages of similar kind. Some benchmarks could be found here.
以下是上述问题的答案
# 1) combinations: without replacement: distinct items
combinations(5, 2)
[,1] [,2]
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 1 5
[5,] 2 3
[6,] 2 4
[7,] 2 5
[8,] 3 4
[9,] 3 5
[10,] 4 5
# 2) combinations: with replacement: distinct items
combinations(5, 2, replace=TRUE)
[,1] [,2]
[1,] 1 1
[2,] 1 2
[3,] 1 3
[4,] 1 4
[5,] 1 5
[6,] 2 2
[7,] 2 3
[8,] 2 4
[9,] 2 5
[10,] 3 3
[11,] 3 4
[12,] 3 5
[13,] 4 4
[14,] 4 5
[15,] 5 5
# 3) combinations: without replacement: non distinct items
combinations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "c"
# 4) combinations: with replacement: non distinct items
combinations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` does not matter
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "b"
[5,] "b" "c"
[6,] "c" "c"
# 5) permutations: without replacement: distinct items
permutations(5, 2)
[,1] [,2]
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 1 5
[5,] 2 1
[6,] 2 3
[7,] 2 4
[8,] 2 5
[9,] 3 1
[10,] 3 2
[11,] 3 4
[12,] 3 5
[13,] 4 1
[14,] 4 2
[15,] 4 3
[16,] 4 5
[17,] 5 1
[18,] 5 2
[19,] 5 3
[20,] 5 4
# 6) permutations: with replacement: distinct items
permutations(5, 2, replace = TRUE)
[,1] [,2]
[1,] 1 1
[2,] 1 2
[3,] 1 3
[4,] 1 4
[5,] 1 5
[6,] 2 1
[7,] 2 2
[8,] 2 3
[9,] 2 4
[10,] 2 5
[11,] 3 1
[12,] 3 2
[13,] 3 3
[14,] 3 4
[15,] 3 5
[16,] 4 1
[17,] 4 2
[18,] 4 3
[19,] 4 4
[20,] 4 5
[21,] 5 1
[22,] 5 2
[23,] 5 3
[24,] 5 4
[25,] 5 5
# 7) permutations: without replacement: non distinct items
permutations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "a"
[5,] "b" "c"
[6,] "c" "a"
[7,] "c" "b"
# 8) permutations: with replacement: non distinct items
permutations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` doesn't matter
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "a"
[5,] "b" "b"
[6,] "b" "c"
[7,] "c" "a"
[8,] "c" "b"
[9,] "c" "c"
与其他软件包比较
与现有软件包相比，使用arrangements几乎没有优势.
Compare to other packages
There are few advantages of using arrangements over the existing packages.
-
集成框架:您不必为不同的方法使用不同的包.
Integral framework: you don't have to use different packages for different methods.
这是非常有效的.参见 https://randy3k.github.io/arrangements/articles/benchmark.html以获得一些基准.
It is very efficient. See https://randy3k.github.io/arrangements/articles/benchmark.html for some benchmarks.
这是高效的内存，它能够生成所有13个！由于矩阵大小的限制，从1到13的置换无法使用，因此现有软件包将无法做到这一点.迭代器的getnext()方法允许用户一个接一个地安排.
It is memory efficient, it is able to generate all 13! permutation of 1 to 13, existing packages will fail to do so because of the limitation of matrix size. The getnext() method of the iterators allow users to get the arrangements one by one.
生成的排列是按字典顺序排列的，对于某些用户来说可能是需要的.
The generated arrangements are in dictionary order which may be desired for some users.
这篇关于有/无替换的排列和组合，用于不同/不明显的项目/多集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
