r - R中零一向量的唯一排列

Question

我的问题如下:

假设我们有一个长度为 n 的向量 (1,1,1,...,0,0) 和 k在一开始的时候。将此向量视为实现了一些变量 L1 到 Ln 的向量。我需要计算的是

对 Function(L1,...,Ln) 的 (1,1,1,...,0,0) 的所有唯一排列求和

我已经搜索了我的问题的解决方案，是的，有一些，只要 n 不是太大，它们就可以工作。

只要 n 低于 30，我的 PC 就不会死机并且以下想法有效:

1) 借助以下代码 (found it here) 创建所有唯一排列的 data.frame

uniqueperm2 <- function(d) {
  dat <- factor(d)
  N <- length(dat)
  n <- tabulate(dat)
  ng <- length(n)
  if(ng==1) return(d)
  a <- N-c(0,cumsum(n))[-(ng+1)]
  foo <- lapply(1:ng, function(i) matrix(combn(a[i],n[i]),nrow=n[i]))
  out <- matrix(NA, nrow=N, ncol=prod(sapply(foo, ncol)))
  xxx <- c(0,cumsum(sapply(foo, nrow)))
  xxx <- cbind(xxx[-length(xxx)]+1, xxx[-1])
  miss <- matrix(1:N,ncol=1)
  for(i in seq_len(length(foo)-1)) {
    l1 <- foo[[i]]
    nn <- ncol(miss)
    miss <- matrix(rep(miss, ncol(l1)), nrow=nrow(miss))
    k <- (rep(0:(ncol(miss)-1), each=nrow(l1)))*nrow(miss) + 
               l1[,rep(1:ncol(l1), each=nn)]
    out[xxx[i,1]:xxx[i,2],] <- matrix(miss[k], ncol=ncol(miss))
    miss <- matrix(miss[-k], ncol=ncol(miss))
  }
  k <- length(foo)
  out[xxx[k,1]:xxx[k,2],] <- miss
  out <- out[rank(as.numeric(dat), ties="first"),]
  foo <- cbind(as.vector(out), as.vector(col(out)))
  out[foo] <- d
  t(out)
}

2) 对该 data.frame 的组件求和

可悲的是，在我的问题中，n 是 100 及以上。对我来说好消息是我实际上不需要我的 RAM 中的整个 data.frame。一个算法会记住最后一个排列，用它来评估 Funktion(L1,...,Ln) 并在循环中计算下一个排列等等就足够了。感谢您的帮助。

编辑Hack-R 要求举个例子，这是我得到的

    > d <- c()
    > d[1:25]=0
    > d[25:50]=1
    > d
     [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> uniqueperm2(d)
Error: cannot allocate vector of size 905608.1 Gb
In addition: Warning messages:
1: In vector("list", count) :
  Reached total allocation of 8109Mb: see help(memory.size)
2: In vector("list", count) :
  Reached total allocation of 8109Mb: see help(memory.size)
3: In vector("list", count) :
  Reached total allocation of 8109Mb: see help(memory.size)
4: In vector("list", count) :
  Reached total allocation of 8109Mb: see help(memory.size)

Answer 1

这是一种遍历排列的方法。我仍然认为有更好的方法，但还没有想出。

此函数查看由 1 和 0 组成的数组，并尽可能尝试将最右边的 1 移到左边。 (基本上将向量视为一个二进制数，并试图找到下一个正好有 n 位的最大数)

next_x <- function(x) {
    i <- tail(which(diff(x)==1),1)
    if (length(i)>0) {
        x[c(i, i+1)]<-c(1,0)
        x[(i+1):length(x)] <- sort(x[(i+1):length(x)])
    } else {
        stop("no more moves")
    }
    x
}

你从 x 开始，然后你可以迭代

x <- c(0,0,0,0,1,1,1)
while(!all(x==c(1,1,1,0,0,0,0))) {
    x <- next_x(x)
    print(x)
}