生成具有例外/条件的独特排列

Question

我遇到了一个需要简化的“计算问题”。似乎讨论了类似的主题（例如这篇post），但我在寻找一个好的示例/解决方案/算法时遇到了问题。

我想要的是生成一种算法，该算法可以找到向量中元素的唯一排列，并且如果满足特定条件则不会生成排列，从而肯定会减少所需的排列和计算的数量。

让我们从一个没有条件/异常的简单示例开始：

找到可以生成独特排列的算法没有问题（例如参见 John D'Errico 的 MATLAB 代码）。假设我们有以下二元向量：

 x = [1,1,0,0]

向量有六种独特的排列，包括向量本身：

y1 = [1,1,0,0]
y2 = [1,0,1,0]
y3 = [1,0,0,1]
y4 = [0,1,1,0]
y5 = [0,1,0,1]
y6 = [0,0,1,1]

根据情况：

我真正想要的是过滤满足特定条件的所有排列： 两个条件的示例：

• 不要生成第 3 列和第 4 列中的值分别为 1 和 0 的排列。
• 不要生成第 1 列和第 2 列中的值分别为 1 和 1 的排列。

在这种情况下，唯一生成的排列应该是：

y3 = [1,0,0,1]
y5 = [0,1,0,1]
y6 = [0,0,1,1]

生成所有排列相当容易，而不仅仅是过滤所有不满足条件的行；但是，我不知道如何生成一个从一开始就排除条件排列的算法......

Answer 1

由于问题中有

r

标签，因此这里有一些基本的 R 实现。

---

• 使用递归，其中标准检查器在

  checker

中设计

f <- function(L, n) {
  p <- seq_len(L)
  init <- rep(0, L)
  # checker function
  checker <- function(v) {
    !(all(v[1:2] == c(1, 1)) || all(v[3:4] == c(1, 0)))
  }

  # helper function for permuation of positions
  helper <- function(n) {
    if (n == 1) {
      return(as.list(p))
    }
    lst <- Recall(n - 1)
    unlist(
      lapply(lst, \(x) {
        u <- p[p > x[length(x)]]
        if (length(u)) {
          Filter(\(k) checker(replace(init, k, 1)), Map(c, x, u))
        }
      }),
      recursive = FALSE
    )
  }

  lapply(helper(n), replace, x = init, value = 1)
}

• 非递归版本，但对所有可能的组合都带有

  combn

  ，更加简洁易懂：

f <- function(L, n) {
  init <- rep(0, L)
  # checker function
  checker <- function(v) {
    !(all(v[1:2] == c(1, 1)) || all(v[3:4] == c(1, 0)))
  }
  Filter(
    length,
    combn(L, 2, \(k) {
      v <- replace(init, k, 1)
      if (checker(v)) v
    }, simplify = FALSE)
  )
}

---

输出

> L <- 4

> n <- 2

> f(L, n)
[[1]]
[1] 1 0 0 1

[[2]]
[1] 0 1 0 1

[[3]]
[1] 0 0 1 1