R - генерировать уникальные последовательности списка с повторным получением элементов

Question

Я хочу сгенерировать уникальные последовательности элементов в списке, где некоторые элементы не являются уникальными в R

sequence <- c(1,0,1,0)

Например:

result<-function(sequence)  
result:
  seq1 seq2 seq3 seq4 seq5 seq6
1    1    1    0    0    0    1
2    0    1    0    1    1    0
3    1    0    1    0    1    0
4    0    0    1    1    0    1

обратите внимание, что все последовательности содержат каждый элементиз исходной последовательности, так что сумма последовательности всегда равна 2

gtools возвращает "слишком мало разных элементов"

result <- gtools::permutations(4, 4, coseq)

Я не нахожу ни одного сообщения SO, которое бы непосредственно решало эту проблему,но вместо этого разрешить повторение элементов: Создание комбинации последовательностей , достижимых с помощью expand.grid и различной длины последовательностей.

РЕДАКТИРОВАТЬ: Вышеприведенный пример является минимальным примером, в идеале он будет работать на последовательности:

 sequence = c(0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1)

Несколько важно, чтобы решение не генерировало дубликаты, которыезатем впоследствии удаляются, так как более длинная последовательность, скажем, 20 или 30, будет очень вычислительно требовательной, если генерируются дубликаты.

Answer 1

m = apply(gtools::permutations(2, 4, 1:4, repeats.allowed = TRUE), 1, function(x) sequence[x])
m[,colSums(m) == 2]
#     [,1] [,2] [,3] [,4] [,5] [,6]
#[1,]    1    1    1    0    0    0
#[2,]    1    0    0    1    1    0
#[3,]    0    1    0    1    0    1
#[4,]    0    0    1    0    1    1

Answer 2

Существует несколько пакетов, специально созданных для этого.

Первый пакет arrangements:

## sequence is a bad name as it is a base R function so we use s instead
s <- c(1,0,1,0)
arrangements::permutations(unique(s), length(s), freq = table(s))
     [,1] [,2] [,3] [,4]
[1,]    1    1    0    0
[2,]    1    0    1    0
[3,]    1    0    0    1
[4,]    0    1    1    0
[5,]    0    1    0    1
[6,]    0    0    1    1

Далее у нас есть RcppAlgos (я автор):

RcppAlgos::permuteGeneral(unique(s), length(s), freqs = table(s))
     [,1] [,2] [,3] [,4]
[1,]    1    1    0    0
[2,]    1    0    1    0
[3,]    1    0    0    1
[4,]    0    1    1    0
[5,]    0    1    0    1
[6,]    0    0    1    1

Они оба очень эффективны. Чтобы дать вам представление, что для реальной потребности со стороны OP другие методы потерпят неудачу (я думаю, что есть ограничение на число строк для матрицы ... 2 ^ 31 - 1, хотя не уверен), или возьмите очень долго, так как им придется генерировать 16! ~= 2.092e+13 перестановок перед дальнейшей обработкой. Однако с этими двумя пакетами возврат мгновенный:

## actual example needed by OP
sBig <- c(0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1)

system.time(a <- arrangements::permutations(unique(sBig), length(sBig), freq = table(sBig)))
user  system elapsed 
0.001   0.001   0.002 

system.time(b <- RcppAlgos::permuteGeneral(unique(sBig), length(sBig), freqs = table(sBig)))
user  system elapsed 
0.001   0.001   0.002 

identical(a, b)
[1] TRUE

dim(a)
[1] 11440    16

Answer 3

Поскольку вы упомянули gtools::permutations, вы можете сделать это

Сначала сгенерируйте все перестановки

m <- apply(permutations(4, 4, 1:length(sequence)), 1, function(x) sequence[x])
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
#[1,]    1    1    1    1    1    1    0    0    0     0     0     0     1     1
#[2,]    0    0    1    1    0    0    1    1    1     1     0     0     1     1
#[3,]    1    0    0    0    0    1    1    0    1     0     1     1     0     0
#[4,]    0    1    0    0    1    0    0    1    0     1     1     1     0     0
#     [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24]
#[1,]     1     1     1     1     0     0     0     0     0     0
#[2,]     0     0     0     0     1     1     0     0     1     1
#[3,]     1     0     1     0     0     1     1     1     1     0
#[4,]     0     1     0     1     1     0     1     1     0     1

Затем удалите дублирующиеся столбцы (из неразличимости 1 и 0)

m[, !duplicated(apply(m, 2, paste, collapse = ""))]
#     [,1] [,2] [,3] [,4] [,5] [,6]
#[1,]    1    1    1    0    0    0
#[2,]    0    0    1    1    1    0
#[3,]    1    0    0    1    0    1
#[4,]    0    1    0    0    1    1