Ответ 1

EDIT: я обновил ответ, чтобы использовать более эффективный пакет arrangements

Начало использования arrangement

arrangements содержит некоторые эффективные генераторы и итераторы для перестановок и комбинаций. Было продемонстрировано, что arrangements превосходит большинство существующих пакетов подобного рода. Некоторые критерии можно найти здесь.

Вот ответы на вышеуказанные вопросы

# 1) combinations: without replacement: distinct items

combinations(5, 2)

      [,1] [,2]
 [1,]    1    2
 [2,]    1    3
 [3,]    1    4
 [4,]    1    5
 [5,]    2    3
 [6,]    2    4
 [7,]    2    5
 [8,]    3    4
 [9,]    3    5
[10,]    4    5


# 2) combinations: with replacement: distinct items

combinations(5, 2, replace=TRUE)

      [,1] [,2]
 [1,]    1    1
 [2,]    1    2
 [3,]    1    3
 [4,]    1    4
 [5,]    1    5
 [6,]    2    2
 [7,]    2    3
 [8,]    2    4
 [9,]    2    5
[10,]    3    3
[11,]    3    4
[12,]    3    5
[13,]    4    4
[14,]    4    5
[15,]    5    5



# 3) combinations: without replacement: non distinct items

combinations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)

     [,1] [,2]
[1,] "a"  "a" 
[2,] "a"  "b" 
[3,] "a"  "c" 
[4,] "b"  "c" 



# 4) combinations: with replacement: non distinct items

combinations(x = c("a", "b", "c"), k = 2, replace = TRUE)  # as `freq` does not matter

     [,1] [,2]
[1,] "a"  "a" 
[2,] "a"  "b" 
[3,] "a"  "c" 
[4,] "b"  "b" 
[5,] "b"  "c" 
[6,] "c"  "c" 

# 5) permutations: without replacement: distinct items

permutations(5, 2)

      [,1] [,2]
 [1,]    1    2
 [2,]    1    3
 [3,]    1    4
 [4,]    1    5
 [5,]    2    1
 [6,]    2    3
 [7,]    2    4
 [8,]    2    5
 [9,]    3    1
[10,]    3    2
[11,]    3    4
[12,]    3    5
[13,]    4    1
[14,]    4    2
[15,]    4    3
[16,]    4    5
[17,]    5    1
[18,]    5    2
[19,]    5    3
[20,]    5    4



# 6) permutations: with replacement: distinct items

permutations(5, 2, replace = TRUE)

      [,1] [,2]
 [1,]    1    1
 [2,]    1    2
 [3,]    1    3
 [4,]    1    4
 [5,]    1    5
 [6,]    2    1
 [7,]    2    2
 [8,]    2    3
 [9,]    2    4
[10,]    2    5
[11,]    3    1
[12,]    3    2
[13,]    3    3
[14,]    3    4
[15,]    3    5
[16,]    4    1
[17,]    4    2
[18,]    4    3
[19,]    4    4
[20,]    4    5
[21,]    5    1
[22,]    5    2
[23,]    5    3
[24,]    5    4
[25,]    5    5


# 7) permutations: without replacement: non distinct items

permutations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)

     [,1] [,2]
[1,] "a"  "a" 
[2,] "a"  "b" 
[3,] "a"  "c" 
[4,] "b"  "a" 
[5,] "b"  "c" 
[6,] "c"  "a" 
[7,] "c"  "b" 



# 8) permutations: with replacement: non distinct items

permutations(x = c("a", "b", "c"), k = 2, replace = TRUE)  # as `freq` doesn't matter

      [,1] [,2]
 [1,] "a"  "a" 
 [2,] "a"  "b" 
 [3,] "a"  "c" 
 [4,] "b"  "a" 
 [5,] "b"  "b" 
 [6,] "b"  "c" 
 [7,] "c"  "a" 
 [8,] "c"  "b" 
 [9,] "c"  "c" 

Сравнить с другими пакетами

Существует несколько преимуществ использования arrangements над существующими пакетами.

• Интегральная структура: вам не нужно использовать разные пакеты для разных методов.

• Это очень эффективно. См. https://randy3k.github.io/arrangements/articles/benchmark.html для некоторых тестов.

• Это эффективная память, она способна генерировать все 13! перестановка с 1 по 13, существующие пакеты не смогут этого сделать из-за ограничения размера матрицы. Метод getnext() итераторов позволяет пользователям получать соглашения по одному.

• Сгенерированные устройства в порядке словаря, которые могут потребоваться для некоторых пользователей.

Ответ 2

Прогулка по кусочку комбинаторики в R *

Ниже мы рассмотрим пакеты, оснащенные возможностями генерации комбинаций и перестановок. Если я упустил какой-либо пакет, пожалуйста, простите меня и, пожалуйста, оставьте комментарий или еще лучше, отредактируйте этот пост.

Схема анализа:

• Введение
  • Обзор
• Комбинация
• Перестановки
• Мультимножества
• Резюме
• Память

Прежде чем мы начнем, заметим, что комбинации/перестановки с заменой отдельных элементов с не-distint, выбранных m за раз, эквивалентны. Это так, потому что, когда у нас есть замена, это не является конкретным. Таким образом, независимо от того, сколько раз изначально возникает определенный элемент, на выходе будет экземпляр этого элемента, повторяющийся 1 - m раз. Соблюдайте (взято из примера # 4 ответа старого от @RandyLai):

library(iterpc)
## non-distinct..  N.B. "a" occurs 2 times
x <- c("a", "a", "b", "c")
I <- iterpc(table(x), 2, replace=TRUE)

getall(I)
    [,1] [,2]
[1,] "a"  "a" 
[2,] "a"  "b" 
[3,] "a"  "c" 
[4,] "b"  "b" 
[5,] "b"  "c" 
[6,] "c"  "c"

## distinct..  N.B. "a" occurs 1 times
x2 <- unique(x)
I2 <- iterpc(table(x2), 2, replace=TRUE)

## same result...
identical(getall(I), getall(I2))
[1] TRUE

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

1. Введение

• gtools v 3.5.0
• combinat v 0.0-8
• iterpc v 0.3.4
• multicool v 0,1-10
• partitions v 1.9-19
• RcppAlgos v 0.2.5 (я автор)
• arrangements v 1.0.1

Я не включил permute или permutations, поскольку они на самом деле не предназначены для атаки на эти типы проблем.

| --------------------------------------- ОБЗОР ---------------------------------------- |

|_______________| gtools | combinat | multicool | partitions | 
|      comb rep |  Yes   |          |           |            | 
|   comb NO rep |  Yes   |   Yes    |           |            | 
|      perm rep |  Yes   |          |           |            |  
|   perm NO rep |  Yes   |   Yes    |    Yes    |    Yes     |
| perm multiset |        |          |    Yes    |            |  
| comb multiset |        |          |           |            |  
|accepts factors|        |   Yes    |           |            |  
|   m at a time |  Yes   |  Yes/No  |           |            |  
|general vector |  Yes   |   Yes    |    Yes    |            |  

|_______________| iterpc | arrangements | RcppAlgos |
|      comb rep |  Yes   |     Yes      |    Yes    |
|   comb NO rep |  Yes   |     Yes      |    Yes    |
|      perm rep |  Yes   |     Yes      |    Yes    |
|   perm NO rep |  Yes   |     Yes      |    Yes    |
| perm multiset |  Yes   |     Yes      |    Yes    |
| comb multiset |  Yes   |     Yes      |    Yes    |
|accepts factors|        |              |    Yes    |
|   m at a time |  Yes   |     Yes      |    Yes    |
|general vector |  Yes   |     Yes      |    Yes    |

Последние две задачи m at a time и general vector относятся к возможности генерации результатов "m за раз" (когда m меньше длины вектора) и перестраивают "общий вектор" в противоположность до 1:n. На практике мы обычно занимаемся поиском перестановок общего вектора, поэтому все рассмотренные ниже исследования отражают это (когда это возможно).

Все тесты были запущены на трех разных настройках.

• Macbook Pro i7 16Gb
• Macbook Air i5 4Gb
• Lenovo Запуск Windows 7 i5 8Gb

Представленные результаты были получены из установки №1 (то есть MBPro). Результаты для двух других систем были схожи. Кроме того, gc() периодически вызывается для обеспечения доступности всей памяти (см. ?gc).

2. Комбинации

Сначала рассмотрим комбинации без замены, выбранные m за раз.

• RcppAlgos
• iterpc
• combinat (или utils)
• gtools
• arrangements

Как сделать:

library(RcppAlgos)
library(gtools)
library(combinat)
library(arrangements)

set.seed(13)
testVector1 <- sort(sample(100, 17))
m <- 9

## RcppAlgos
          ###  Your vector goes here    
          ###          |    
          ###          V  
t1 <- comboGeneral(testVector1, m)  ## returns matrix with m columns

## iterpc
            ###   Length        Your vector goes here    
            ###     |                    |    
            ###     V                    V  
t2 <- getall(iterpc(17, m, labels = testVector1))  ## returns matrix with m columns
identical(t1, t2)
[1] TRUE

## combinat
    ###  Your vector goes here    
    ###          |    
    ###          V  
t3 <- combn(testVector1, m)  ## returns matrix with m rows

## gtools
                    ###  Length  vector goes here    
                    ###    |           |    
                    ###    V           V  
t4 <- gtools::combinations(17, m, testVector1)  ## returns matrix with m columns
identical(t(t3), t4) ## must transpose to compare
[1] TRUE

## arrangements.. similar to gtools
t5 <- arrangements::combinations(17, m, testVector1)
identical(t1, t5)
[1] TRUE

Ориентиры:

library(microbenchmark)
microbenchmark(cbRcppAlgos = comboGeneral(testVector1, m),
               cbIterpc = getall(iterpc(17, m, labels = testVector1)),
               cbGtools = gtools::combinations(17, m, testVector1),
               cbCombinat = combn(testVector1, m),
               cbArrangements = arrangements::combinations(17, m, testVector1),
               unit = "relative")
 Unit: relative
          expr        min         lq       mean     median         uq       max neval
   cbRcppAlgos   1.000000   1.000000   1.000000   1.000000   1.000000  1.000000   100
      cbIterpc   7.782878   8.132294  10.009169  10.516546   6.197653 30.239650   100
      cbGtools 301.838057 280.863347 199.243533 276.414159 144.757765 77.340552   100
    cbCombinat  66.850014  66.895874  55.225608  68.419620  36.924797 42.437841   100
cbArrangements   1.391088   1.365510   2.001724   1.413413   1.206996  4.637802   100

Теперь мы рассмотрим комбинации с заменой, выбранной m за раз.

• RcppAlgos
• iterpc
• gtools
• arrangements

Как сделать:

set.seed(97)
testVector2 <- sort(rnorm(10))
m <- 8

## RcppAlgos
                            ###  Set repetition to TRUE
                            ###          |    
                            ###          V
t1 <- comboGeneral(testVector2, m, repetition = TRUE)

## iterpc
                                ###           Set replace to TRUE
                                ###                    |    
                                ###                    V
t2 <- getall(iterpc(10, m, labels = testVector2, replace = TRUE))
identical(t1, t2)
[1] TRUE

## gtools
                                     ###   Set repeats.allowed to TRUE
                                     ###               |    
                                     ###               V  
t3 <- gtools::combinations(10, m, testVector2, repeats.allowed = TRUE)
identical(t1, t3)
[1] TRUE


## arrangements.. similar to iterpc
t4 <- arrangements::combinations(10, m, testVector2, replace = TRUE)
identical(t1, t4)
[1] TRUE

Контрольные показатели:

gc()
microbenchmark(cbRcppAlgos = comboGeneral(testVector2, m, TRUE),
               cbIterpc = getall(iterpc(10, m, labels = testVector2, replace = TRUE)),
               cbGtools = gtools::combinations(10, m, testVector2, repeats.allowed = TRUE),
               cbArrangements = arrangements::combinations(10, m, testVector2, replace = TRUE),
               unit = "relative")
Unit: relative
           expr        min         lq      mean    median        uq       max neval
    cbRcppAlgos   1.000000   1.000000  1.000000  1.000000  1.000000  1.000000   100
       cbIterpc   6.889983   9.615315  5.384619  3.985531  4.270222  8.695109   100
       cbGtools 235.985450 230.144286 95.180495 77.352867 78.607296 21.490131   100
 cbArrangements   1.186165   1.213644  1.714389  1.051762  1.076142  8.365345   100

3. Перестановки

Сначала рассмотрим перестановки без замены, выбранные m за раз.

• RcppAlgos
• iterpc
• gtools
• arrangements

Как сделать:

testVector3 <- as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29))

## RcppAlgos... permuteGeneral same as comboGeneral above
t1 <- permuteGeneral(testVector3, 6)

## iterpc.. use the ordered argument
t2 <- getall(iterpc(10, 6, labels = testVector3,  ordered = TRUE))
identical(t1[do.call(order,as.data.frame(t1)),],
          t2[do.call(order,as.data.frame(t2)),])
[1] TRUE

## gtools... permutations same as combinations above
t3 <- gtools::permutations(10, 6, testVector3)
identical(t2,t3)
[1] TRUE

## arrangements... similar to gtools
t4 <- arrangements::permutations(10, 6, testVector3)
identical(t2,t4)
[1] TRUE

Ориентиры:

gc()
microbenchmark(cbRcppAlgos = permuteGeneral(testVector3, 6),
               cbIterpc = getall(iterpc(10, 6, labels = testVector3, ordered = TRUE)),
               cbGtools = gtools::permutations(10, 6, testVector3),
               cbArrangements = arrangements::permutations(10, 6, testVector3),
               unit = "relative")
Unit: relative
           expr        min        lq       mean    median        uq       max neval
    cbRcppAlgos   1.131699  0.869670  0.8226483  1.064050  1.005817 0.9449483   100
       cbIterpc   3.888463  3.659348  3.0571884  3.600888  3.737414 1.2014912   100
       cbGtools 120.111236 78.578038 50.0463422 65.601480 63.006308 4.9063842   100
 cbArrangements   1.000000  1.000000  1.0000000  1.000000  1.000000 1.0000000   100

Далее мы рассмотрим перестановки без замены общим вектором (возвращаем все перестановки).

• RcppAlgos
• iterpc
• gtools
• combinat
• multicool
• arrangements

Как сделать:

library(multicool)
testVector3Prime <- testVector3[1:7]

## For RcppAlgos, iterpc, & gtools (see above)

## combinat
t4 <- permn(testVector3Prime) ## returns a list of vectors

## convert to a matrix
t4 <- do.call(rbind, t4)

## multicool.. we must first call initMC
t5 <- allPerm(initMC(testVector3Prime)) ## returns a matrix with n columns

all.equal(t4[do.call(order,as.data.frame(t4)),],
          t5[do.call(order,as.data.frame(t5)),])
[1] TRUE

Ориентиры:

gc()
microbenchmark(cbRcppAlgos = permuteGeneral(testVector3Prime, 7),
               cbIterpc = getall(iterpc(7, labels = testVector3Prime, ordered = TRUE)),
               cbGtools = gtools::permutations(7, 7, testVector3Prime),
               cbCombinat = permn(testVector3Prime),
               cbMulticool = allPerm(initMC(testVector3Prime)),
               cbArrangements = arrangements::permutations(7, 7, testVector3Prime),
               unit = "relative")
Unit: relative
           expr         min          lq       mean     median         uq        max neval
    cbRcppAlgos    1.895268    1.648268   1.338422   1.448837   1.439690  0.1552207   100
       cbIterpc    6.903009    6.176998   4.598060   5.343690   5.669562  0.4968279   100
       cbGtools  594.775019  458.971080 330.557977 388.202185 363.622699 49.1267936   100
     cbCombinat  149.297281  121.125292  87.994595 103.359899  98.659190 13.4736489   100
    cbMulticool 1379.559854 1080.910453 768.062424 925.422114 868.249803 82.6572008   100
 cbArrangements    1.000000    1.000000   1.000000   1.000000   1.000000  1.0000000   100

Теперь мы рассмотрим перестановки без замены для 1:n (возвращаем все перестановки).

• RcppAlgos
• iterpc
• gtools
• combinat
• multicool
• partitions
• arrangements

Как сделать:

library(partitions)
## For RcppAlgos, iterpc, gtools, combinat, & multicool (see above)

## partitions
#    Enter length here
#           |
#           V
t1 <- perms(7)  ## returns an object of type 'partition' with n rows

identical(t(as.matrix(t1)), permutations(7,7))
[1] TRUE

Ориентиры:

gc()
microbenchmark(cbRcppAlgos = permuteGeneral(7, 7),
               cbIterpc = getall(iterpc(7, ordered = TRUE)),
               cbGtools = gtools::permutations(7, 7),
               cbCombinat = permn(7),
               cbMulticool = allPerm(initMC(1:7)),
               cbPartitions = perms(7),
               cbArrangements = arrangements::permutations(7, 7),
               unit = "relative")
Unit: relative
           expr         min          lq       mean     median         uq        max neval
    cbRcppAlgos    1.965664    1.645951   1.639419   1.483691   1.493001   1.426212   100
       cbIterpc    4.679192    4.273127   3.670478   3.851531   3.835654   2.228578   100
       cbGtools  615.989876  467.483135 400.614961 407.215566 405.084243 249.207568   100
     cbCombinat  155.239836  123.209368 106.005735 106.019798 106.544329  87.583616   100
    cbMulticool 1460.828463 1098.216653 947.948907 953.747231 941.274883 759.183167   100
   cbPartitions    1.663103    1.435245   1.672774   1.274886   1.657171   1.717215   100
 cbArrangements    1.000000    1.000000   1.000000   1.000000   1.000000   1.000000   100

Наконец, рассмотрим перестановки с заменой.

• RcppAlgos
• iterpc
• gtools
• arrangements

Как сделать:

t1 <- permuteGeneral(testVector3, 5, repetition = TRUE)
t2 <- getall(iterpc(10, 5, labels = testVector3, ordered = TRUE, replace = TRUE))
identical(t1[do.call(order,as.data.frame(t1)),],
          t2[do.call(order,as.data.frame(t2)),])
[1] TRUE

t3 <- gtools::permutations(10, 5, testVector3, repeats.allowed = TRUE)
identical(t2, t3)
[1] TRUE

t4 <- arrangements::permutations(10, 5, testVector3, replace = TRUE)
identical(t2, t4)
[1] TRUE

Этот следующий тест немного удивителен, учитывая результаты до сих пор.

gc()
microbenchmark(cbRcppAlgos = permuteGeneral(testVector3, 5, TRUE),
               cbIterpc = getall(iterpc(10, 5, labels = testVector3, ordered = TRUE, replace = TRUE)),
               cbGtools = gtools::permutations(10, 5, testVector3, repeats.allowed = TRUE),
               cbArrangements = arrangements::permutations(10, 5, testVector3, replace = TRUE),
               unit = "relative")
Unit: relative
           expr      min        lq     mean   median       uq      max neval
    cbRcppAlgos 1.000000 1.0000000 1.000000 1.000000 1.000000 1.000000   100
       cbIterpc 7.114755 6.6201796 5.512014 5.328362 5.487741 2.525771   100
       cbGtools 1.399341 1.4885995 1.652809 1.578265 1.651103 1.284924   100
 cbArrangements 1.036266 0.9670526 0.995044 1.012060 1.020751 1.100233   100

Это не опечатка... gtools::permutations почти так же быстро, как RcppAlgos::permuteGeneral и почти в 4 раза быстрее, чем предложение iterpc. Я рекомендую читателю проверить исходный код gtools::permutations, поскольку он является одним из самых элегантных дисплеев программирования там (R или иначе).

4. Мультимножества

Сначала рассмотрим комбинации мультимножеств.

• RcppAlgos
• iterpc
• arrangements

Чтобы найти комбинации/перестановки мультимножеств, с RcppAlgos используйте аргументы freqs, чтобы указать, сколько раз повторяется каждый элемент исходного вектора v. Для iterpc просто введите частоты в качестве аргумента n.

set.seed(496)
myFreqs <- sample(1:5, 10, replace = TRUE)

## This is how many times each element will be repeated
myFreqs
[1] 2 4 4 5 3 2 2 2 3 4

testVector4 <- as.integer(c(1, 2, 3, 5, 8, 13, 21, 34, 55, 89))

t1 <- comboGeneral(testVector4, 12, freqs = myFreqs)

t2 <- getall(iterpc(myFreqs, 12, labels = testVector4))
identical(t1[do.call(order,as.data.frame(t1)),],
          t2[do.call(order,as.data.frame(t2)),])
[1] TRUE

t3 <- arrangements::combinations(freq = myFreqs, k = 12, x = testVector4)
identical(t2, t3)
[1] TRUE

Ориентиры:

gc()
microbenchmark(cbRcppAlgos = comboGeneral(testVector4, 12, freqs = myFreqs),
               cbIterpc = getall(iterpc(myFreqs, 12, labels = testVector4)),
               cbArrangements = arrangements::combinations(freq = myFreqs, k = 12, x = testVector4),
               unit = "relative")
Unit: relative
           expr      min       lq      mean   median       uq        max neval
    cbRcppAlgos 1.048697 1.035022 0.8044517 1.093056 1.084075 0.05688653   100
       cbIterpc 5.941140 5.773291 4.8479643 5.804056 5.282206 1.14469884   100
 cbArrangements 1.000000 1.000000 1.0000000 1.000000 1.000000 1.00000000   100

Для перестановок мультимножеств, выбранных m за раз, имеем:

• RcppAlgos
• iterpc
• arrangements

Как сделать:

set.seed(8128)
myFreqs <- sample(1:3, 5, replace = TRUE)
testVector5 <- sort(runif(5))

myFreqs
[1] 2 2 2 1 3

t1 <- permuteGeneral(testVector5, 7, freqs = myFreqs)

t2 <- getall(iterpc(myFreqs, 7, labels = testVector5, ordered = TRUE))
identical(t1[do.call(order,as.data.frame(t1)),],
          t2[do.call(order,as.data.frame(t2)),])
[1] TRUE

t3 <- arrangements::permutations(freq = myFreqs, k = 7, x = testVector5)
identical(t2, t3)
[1] TRUE

Ориентиры:

gc()
microbenchmark(cbRcppAlgos = permuteGeneral(testVector5, 7, freqs = myFreqs),
               cbIterpc = getall(iterpc(myFreqs, 7, labels = testVector5, ordered = TRUE)),
               cbArrangements = arrangements::permutations(freq = myFreqs, k = 7, x = testVector5),
               unit = "relative")
Unit: relative
           expr       min        lq     mean   median       uq      max neval
    cbRcppAlgos  1.000000  1.000000 1.000000 1.000000 1.000000 1.000000   100
       cbIterpc 11.289073 12.138475 6.429559 5.695491 5.933823 3.117787   100
 cbArrangements  1.059121  1.072712 1.059636 1.017834 1.052349 1.015524   100

Для перестановок мультимножеств, возвращающих все перестановки, имеем:

• RcppAlgos
• iterpc
• multicool
• arrangements

Как сделать:

myFreqs2 <- c(2,1,2,1,2)
testVector6 <- (1:5)^3

## For multicool, you must have the elements explicitly repeated
testVector6Prime <- rep(testVector6, times = myFreqs2)
t3 <- allPerm(initMC(testVector6Prime))

## for comparison
t1 <- permuteGeneral(testVector6, freqs = myFreqs2)
identical(t1[do.call(order,as.data.frame(t1)),],
          t3[do.call(order,as.data.frame(t3)),])
[1] TRUE

Ориентиры:

gc()
microbenchmark(cbRcppAlgos = permuteGeneral(testVector6, freqs = myFreqs2),
               cbIterpc = getall(iterpc(myFreqs2, labels = testVector6, ordered = TRUE)),
               cbMulticool = allPerm(initMC(testVector6Prime)),
               cbArrangements = arrangements::permutations(freq = myFreqs2, x = testVector6),
               unit = "relative")
Unit: relative
           expr         min          lq       mean      median         uq        max neval
    cbRcppAlgos    1.000000    1.000000   1.000000    1.000000   1.000000   1.000000   100
       cbIterpc   11.856884   12.450573  10.149731   11.058266   5.888962  25.620137   100
    cbMulticool 1565.902133 1374.679285 841.652157 1140.371227 509.420100 626.352019   100
 cbArrangements    1.298897    1.381427   1.288668    1.410184   1.122621   2.747879   100

5. Резюме

Оба gtools и combinat являются хорошо установленными пакетами для переупорядочения элементов вектора. С помощью gtools есть еще несколько опций (см. Обзор выше) и combinat, вы можете изменить factors. С помощью multicool можно переставить мультимножества. Хотя partitions ограничен для целей этого вопроса, это мощный блок с высокоэффективными функциями для работы с... вы догадались... разделы.

arrangements

• Вывод находится в порядке словаря.
• Позволяет пользователю указать формат с помощью аргумента type (r = row-major, c = column-major и l = list).
• Предлагает удобные методы, такие как collect и getnext при работе с итераторами.
• Позволяет генерировать комбинацию/перестановки более 2^31 - 1 через getnext. Нотабене multicool также может выполнять это через nextPerm, хотя это может занять довольно много времени (см. выше тесты).
• Говоря о getnext, эта функция позволяет указать определенное количество результатов, используя аргумент d.

Заметим:

icomb <- icombinations(1000, 7)
icomb$getnext(d = 5)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    2    3    4    5    6    7
[2,]    1    2    3    4    5    6    8
[3,]    1    2    3    4    5    6    9
[4,]    1    2    3    4    5    6   10
[5,]    1    2    3    4    5    6   11

Эта функция действительно приятна, когда вам нужно только несколько комбинаций/перестановок. С помощью традиционных методов вам нужно будет сгенерировать все комбинации/перестановки, а затем подмножество. Это сделало бы предыдущий пример невозможным, так как есть больше, чем 10^17 результатов (т.е. choose(1000, 7) = 1.942806e+17).

Эта функция наряду с улучшениями генераторов в arrangements, позволяет ей быть очень эффективной в отношении памяти.

RcppAlgos

• Есть некоторые действительно хорошие функции ограничения, которые мы не будем обсуждать здесь, поскольку они не относятся к теме для этого вопроса. Отмечу только, что типы проблем, которые могут быть решены с помощью этих функций, были мотивацией для создания этого пакета.
• Существует аргумент rowCap, аналогичный аргументу d getnext.

Заметим:

comboGeneral(1000, 7, rowCap = 5)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    2    3    4    5    6    7
[2,]    1    2    3    4    5    6    8
[3,]    1    2    3    4    5    6    9
[4,]    1    2    3    4    5    6   10
[5,]    1    2    3    4    5    6   11

3. Все комбинаторные функции работают с факторами в дополнение к типам данных, принятым в arrangements (т.е. целочисленным, числовым и символьным).

Заметим:

## class and levels are preserved
comboGeneral(factor(letters[1:5], ordered = TRUE), 4)
     [,1] [,2] [,3] [,4]
[1,] a    b    c    d   
[2,] a    b    c    e   
[3,] a    b    d    e   
[4,] a    c    d    e   
[5,] b    c    d    e   
Levels: a < b < c < d < e

## factors get converted to integers in arrangements
arrangements::combinations(5, 4, x = factor(letters[1:5], ordered = TRUE))
     [,1] [,2] [,3] [,4]
[1,]    1    2    3    4
[2,]    1    2    3    5
[3,]    1    2    4    5
[4,]    1    3    4    5
[5,]    2    3    4    5

Если вам интересно, как масштабируется каждый пакет, я оставлю вас с этим последним примером, который измеряет, насколько быстро каждый пакет может генерировать более 100 миллионов результатов (NB gtools::combinations здесь отсутствует, поскольку он будет вызывать ошибку: evaluation nested too deeply...). Кроме того, мы явно вызываем combn из пакета utils, потому что мне не удалось получить успешный запуск из combinat::combn. Различия в использовании памяти между этими двумя довольно странно, учитывая, что они незначительно отличаются (см. ?utils::combn в разделе "Авторы" ).

Для каждого прогона ниже, после выполнения .rs.restartR(), , вы должны дождаться перезапуска R перед запуском любого теста. Кроме того, вы должны ждать не менее 2 секунд после выполнения каждого вызова при профилировании памяти, чтобы у профайлера было достаточно времени для сбора информации из стека вызовов.

Заметим:

rm(I,I2,t1,t2,t3,t4,t5,m,myFreqs,myFreqs2,testVector1,
   testVector2,testVector3,testVector4,testVector5,
   testVector6,testVector6Prime,testVector3Prime,x,x2)
gc()
.rs.restartR()
set.seed(2187)
testVector7 <- sort(sample(10^7, 10^3))
system.time(utils::combn(testVector7, 3))
   user  system elapsed 
101.021   0.556 101.634

## call garbage collection to ensure clean memory
gc()
.rs.restartR()
system.time(RcppAlgos::comboGeneral(testVector7, 3))
 user  system elapsed 
1.021   0.451   1.476

gc()
.rs.restartR()
system.time(iterpc::getall(iterpc::iterpc(10^3, 3, labels = testVector7)))
 user  system elapsed 
9.318   1.976  11.356

gc()
.rs.restartR()
system.time(arrangements::combinations(10^3, 3, testVector7))
 user  system elapsed 
1.787   0.471   2.262

6. Память

При выполнении comboGeneral, а также arrangements::combinations память выпрыгивает почти на 2 Gbs, прежде чем вызывать gc. Это кажется правильным как #rows * #nols * bytesPerCell / 2^30 bytes = choose(1000,3) * 3 * 4 / 2^30 bytes = (166167000 * 3 * 4)/2^30 = 1.857 Gbs). Однако при выполнении getall(iterpc память перескакивает через 6 Gbs каждый раз и с combn поведение было стильным (например, иногда оно использовало бы все 16 ГБ памяти, а в других случаях оно могло бы только нанести пару Gbs). Когда я тестировал это в настройке Windows, он часто выходил из строя.

Мы можем подтвердить это, используя Rprof вместе с summaryRporf. Обратите внимание:

gc()
.rs.restartR()
Rprof("RcppAlgos.out", memory.profiling = TRUE)
t1 <- RcppAlgos::comboGeneral(testVector7, 3)
Rprof(NULL)
summaryRprof("RcppAlgos.out", memory = "both")$by.total
                          total.time total.pct mem.total self.time self.pct
".Call"                         1.14       100    1902.5      1.14      100

rm(t1)
gc()
.rs.restartR()
Rprof("iterpc.out", memory.profiling = TRUE)
t2 <- iterpc::getall(iterpc::iterpc(10^3, 3, labels = testVector7))
Rprof(NULL)
summaryRprof("iterpc.out", memory = "both")$by.total
                    total.time total.pct mem.total self.time self.pct
"getall"                  7.70    100.00    7609.5      0.00     0.00

rm(t2)
gc()
.rs.restartR()
Rprof("arrangements.out", memory.profiling = TRUE)
t3 <- arrangements::combinations(10^3, 3, testVector7)
Rprof(NULL)
summaryRprof("arrangements.out", memory = "both")$by.total
                             total.time total.pct mem.total self.time self.pct
".Call"                            2.08     99.05    1901.6      2.08    99.05

rm(t3)
gc()

С RcppAlgos и arrangements, mem.total регистрируется только над 1900 Mb, а для iterpc он регистрирует 7609.5 Mb (около 4x объема памяти).

И вот профиль памяти на меньшем векторном сравнении gtools, utils и combinat.

testVector7Prime <- testVector7[1:300]

.rs.restartR()
Rprof("combinat.out", memory.profiling = TRUE)
t3 <- combinat::combn(testVector7Prime, 3)
Rprof(NULL)
summaryRprof("combinat.out", memory = "both")$by.total
                  total.time total.pct mem.total self.time self.pct
"combinat::combn"      23.40     99.91   10977.8     21.82    93.17

rm(t3)
gc()
.rs.restartR()
Rprof("utils.out", memory.profiling = TRUE)
t4 <- utils::combn(testVector7Prime, 3)
Rprof(NULL)
summaryRprof("utils.out", memory = "both")$by.total
               total.time total.pct mem.total self.time self.pct
"utils::combn"        3.0    100.00     985.3       2.9    96.67

rm(t4)
gc()
.rs.restartR()
Rprof("gtools.out", memory.profiling = TRUE)
t5 <- gtools::combinations(300, 3, testVector7Prime)
Rprof(NULL)
summaryRprof("gtools.out", memory = "both")$by.total
                      total.time total.pct mem.total self.time self.pct
"rbind"                     10.60     99.81    3367.1      9.98    93.97

Интересно, что utils::combn использует около 1/10 памяти как combinat::combn и работает почти на 8 раз быстрее. Это не задерживается с меньшими векторами:

microbenchmark(combinat::combn(2:13, 6), utils::combn(2:13, 6))
Unit: microseconds
                    expr     min      lq     mean  median       uq      max neval
combinat::combn(2:13, 6) 527.378 567.946 629.1268 577.163 604.3270 1816.744   100
   utils::combn(2:13, 6) 663.150 712.872 750.8008 725.716 771.1345 1205.697   100

И с gtools общая используемая память немного меньше 3x, чем utils. Следует отметить, что для этих 3 пакетов я получал разные результаты каждый раз, когда я их запускал (например, для combinat::combn иногда я получал бы 9000 Мб, а затем получаю 13000 Мб).

Тем не менее, ни один из них не может соответствовать RcppAlgos ИЛИ arrangements. Оба используют только 51 Мб при запуске в примере выше.

_{*: Уважение к A Прогулка по комбинаторике Миклоша Боны}