如何生成一个向量的所有组合

Question

如何生成一个向量的所有组合

3

假设我有3个绿色球，2个橙色球和8个黄色球。我想对它们进行排序，如何生成所有可能的序列，假设相同颜色的球是相同的。

在R中，使用gregmisc，我可以这样做

balls<-c('orange','orange', 'green', 'green','green','yellow'...'yellow')

然后只需执行

g <- permutations(length(balls),length(balls),v=balls,set=F)
g.reduced <- g[!duplicated(g),]

但那似乎非常不必要。

- JoshDG

如果您的颜色向量是v，只需执行以下操作： g <- unique(permutations(length(v),length(v),v,F))。一行代码即可。 - jclancy

肯定更易读，但是这仍然无法消除计算重复项的额外计算工作。随着v的长度变得越来越大，这可能不可行。 - JoshDG

好的，这个算法怎么样？为了简单起见，我假设只有一个重复元素，但我认为推广它不会有问题。首先将所有元素“unique”，然后计算排列组合。你会得到一个矩阵，其中包含其他元素的排列组合和之前不唯一的元素之一。将每一行扩展成长度为m + 1 + n - 1的向量，其中n是之前不唯一的元素数量，m是其他元素的数量。从末尾开始的第m + 1个元素开始，将第一个元素放在原始行中，并遍历所有可能的情况。 - jclancy

原始行中元素之间的间距，在n - 1个其他元素之间填充。这个想法是排列矩阵给出了一个顺序，你用重复的n - 1个元素填充可能的空白。我会尝试编写代码或伪代码，并将其放在答案中。 - jclancy

2

这可能是与此处相同的问题：在R中对向量进行所有唯一枚举的排列：https://dev59.com/FW035IYBdhLWcg3wBLRL - Aaron left Stack Overflow

1个回答

阿里云服务器只需要99元/年，新老用户同享，点击查看详情

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

可以查看英文原文，

- jclancy · Answer 1

这是我能想到的最明显的方法。这是我从上面的评论中得出的方法，但我删除了向量中所有非唯一元素的条目，而不是除了一个之外的所有条目。如果我留下一个，这种方法将导致每个条目的一个副本。

arr  # one of the rows of the matrix of permutations
l  # the length of the original un-unique'd vector
out <- list()
vec <- vector(length=l)
find.placings <- function(start, pos, vec, m) {
    if (m == 0)
        return(vec)
    for (i in pos:(l - m + 1)) {
        vec[i] <- arr[start]
        out[[length(out) + 1]] <- find.placings(start + 1, i + 1, vec, m - 1)
    }
}

当然，由于这是高度递归的，请小心使用。我也没有测试过它。如果您想调用该函数，请给出原始值:(1, 1, vector(length=l), m)。