为长度为 k 的向量找到 n 个可能值的所有非等价排列

Question

我有一个函数接受长度为 k 的输入向量，其中向量中的每个元素最多可以有 n 个值。

一般k在6:10范围内，n在2:(k-1).

范围内

对于任何给定的 (n,k)，将有 n^k-1 个可能向量的排列。

目前我正在将每个整数 0:(n^k-1) 映射到一个唯一的排列，并评估该排列的函数以找到所有可能向量的最佳输入向量。

例如，当 n=3 且 k=6 时，映射为：

0:1,1,1,1,1,1
1:1,1,1,1,1,2
2:1,1,1,1,1,3 
3:1,1,1,1,2,1
...
728:3,3,3,3,3,3

但是，就我的目的而言，某些排列是等价的。您可以将向量视为 n classes.

中 k 个元素的分配

两个排列 A 和 B 是等价的，如果以下都成立：

All elements in A that share a class, also share a class in B.

All elements in A that do not share a class, also do not share a class in B.

例如：当 n=2 且 k=6 时，向量

1,2,1,1,2,1 
2,1,2,2,1,2

是等价的。在这两个向量中，元素 {1,3,4,6} 共享一个 class 并且元素 {2,5} 共享一个 class.

当 n=3 且 k=6 时，向量

1,2,3,1,2,3
1,3,2,1,3,2
2,3,1,2,3,1
2,1,3,2,1,3
3,2,1,3,2,1
3,1,2,3,1,2

都是等价的。

我的目标是找到一种比尝试范围 1:(n^k-1) 中的每个输入更有效的方法来找到最佳向量。

我可以看到两种可能的前进方式：

方案一，枚举出每一种可能性，然后过滤掉所有等价的向量。

方案二：缩小我需要提前检查的范围。例如，对于 n=3、k=6，我相当有信心（但尚未证明）我不需要检查 161:1、2、3、3、3、3 以上的任何内容也应该是 1:161 范围内的一些等效排列。

我更喜欢选项 2。

理想的解决方案是 (n,k) 的函数，它输出表示 1:n^k-1 中我需要检查的间隔的向量列表。几乎同样好的是 (n,k) 的函数，它输出我需要检查的 1:n^k-1 中最大的 integer/vector。

作为起点，这里有一些示例 R 代码：

vectorFromID <- function(id, n, k) {
  if(id >= n^k) {
    stop('ID too large!')
  }
  remainder <- id
  elements <- list()
  for(i in (k-1):0) {
    elements[[k-i]] <- (remainder  %/% (n ^ i))+1
    remainder <- remainder %% (n ^ i)
  }
  return(unlist(elements))
}

vectorToID <- function(inputVector, n, k) {
  total <- 0
  for(i in 0:(k-1)) {
    total <- total + (inputVector[i+1]-1) * (n ^ ((k-1)-i))
  }
  return(total)
}

# generate all possible vectors for n=3, k=6
all_vectors <- Map(function(x) vectorFromID(x, 3, 6), 0:728)

编辑以添加递归解决方案的 R 实现，以及两个解决方案的基准测试。

enum <- function(v=NULL, n, k, maxv=0) {
  if (k == 0) {
    return(list(v))
  } else {
    acc <- list()
    for (i in 1:min(n, maxv+1)) {
      acc <- c(acc, enum(c(v,i), n, k-1, max(i,maxv)))
    }
    return(acc)
  }
}
res2 <- enum(NULL, 3, 6, 0)

两种解决方案产生相同的输出，但对于较大的 k 和 n 值，递归解决方案要快得多。下面，time1 是指递归解决方案所花费的时间（以秒为单位）。

n: 2 k: 6 rows1: 32 rows2: 32 match: TRUE time1: 0.02 time2: 0.05
n: 3 k: 6 rows1: 122 rows2: 122 match: TRUE time1: 0 time2: 0.51
n: 4 k: 6 rows1: 187 rows2: 187 match: TRUE time1: 0.01 time2: 3.32
n: 5 k: 6 rows1: 202 rows2: 202 match: TRUE time1: 0 time2: 16.8
n: 2 k: 7 rows1: 64 rows2: 64 match: TRUE time1: 0.02 time2: 0.11
n: 3 k: 7 rows1: 365 rows2: 365 match: TRUE time1: 0 time2: 1.83
n: 4 k: 7 rows1: 715 rows2: 715 match: TRUE time1: 0.05 time2: 19.62
n: 5 k: 7 rows1: 855 rows2: 855 match: TRUE time1: 0.04 time2: 277.81

Answer 1

我还没有完全测试过这个，但我认为它可以满足您的需求。我有三个主要步骤：

应用 expand.grid 提供 n 和 k 的所有可能排列。
将值转化为因子，级别基于出现的顺序。然后，将它们转回数值（在循环中）。例如由于因子水平的顺序相似，c(1,2,3,1,2,3) 和 c(3,2,1,3,2,1) 将返回为 c(1,2,3,1,2,3) 和 c(1,2,3,1,2,3)（即等效）。
Return 唯一的组合。使用 n=3 和 k=6，唯一组合的数量从 729 减少到 162：

函数`combnmix`:

combnmix <- function(n,k){
  tmp <- lapply(as.list(rep(n, k)), seq)
  res1 <- expand.grid(tmp)
  res2 <- NaN*res1
  for(i in seq(nrow(res1))){
    levs <- unique(c(res1[i,]))
    res2[i,] <- as.numeric(factor(res1[i,], levels=levs))
  }
  res3 <- unique(res2)
  res3
}

res <- combnmix(3,6)
res

Answer 2

让我们首先为每个等价物选择一个代表 class。假设向量 p = {x_1 ... x_k} 是一个代表，如果它是所有 p_i 中的字典序最小值使得 p_i ~ p.

请注意，对于所有 j < i，x_i 在范围 (1..x_j + 1) 内。如果这不成立，那么我们可以构造等价的 p_i ，它在字典序上小于 p 。（x_1 = 1 同理）

另外，如果对于每个i，x_i在范围(1..x_j + 1)内，那么p就是一个代表。否则有一些 q = {y_1 ... y_n}，这样对于一些 k，y_i = x_i 对于所有 i < k 和 y_k < x_k。但是对于那个 k，来自 (1..max(x_i)) 的所有值都在 p 的前 k-1 个元素中。所以是y_k。但这证明 p 不等同于 q.

所以 p 是一个代表，当且仅当 x_i 在范围 (1..x_j + 1) 内，对于所有 j < i。然后我们可以用一个简单的递归过程推导出所有这样的代表。抱歉，我的代码示例是用 C++ 编写的，我不知道 R:

void printResult(std::vector<int>& v){
    for (auto val : v){
        std::cout << val << ' ';
    }
    std::cout << '\n';
}

void enumerate(std::vector<int>& v, int n, int k, int max){
    if (k == 0){
        printResult(v);
    } else {
        for (int i = 1; i <= std::min(n, max + 1); i++){
            v.push_back(i);
            enumerate(v, n, k - 1, std::max(i, max));
            v.pop_back();
        }
    }
}

void solve(int n, int k){
    std::vector<int> v;
    enumerate(v, n, k, 0);
}

为长度为 k 的向量找到 n 个可能值的所有非等价排列

Finding all non-equivalent permutations for vectors of length k taking n possible values

algorithm

r

function

permutation

combinatorics

函数`combnmix`:

为长度为 k 的向量找到 n 个可能值的所有非等价排列

Finding all non-equivalent permutations for vectors of length k taking n possible values

algorithm

r

function

permutation

combinatorics

函数combnmix:

函数`combnmix`: