Генерация перестановок в последовательном порядке - R

Question

Я ранее задавал следующий вопрос Перестановка n бернуллиевских случайных величин в R

Ответ на этот вопрос прекрасно работает, если n относительно мало (<30), в противном случае возникает следующий код ошибки Ошибка: невозможно выделить вектор размером 4,0 Гб. Я могу заставить код работать с несколько большими значениями, используя мой рабочий стол на работе, но в итоге возникает та же ошибка. Даже для значений, которые мой компьютер может обрабатывать, скажем, 25, код очень медленный. </p>

Цель этого кода состоит в том, чтобы вычислить разницу между CDF точного распределения (следовательно, перестановок) и нормального приближения. Я случайным образом генерирую некоторые данные, вычисляю статистику теста, а затем мне нужно определить CDF путем суммирования всех перестановок, которые приводят к меньшему значению статистики теста, деленному на общее количество перестановок.

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

Короче говоря: мне нужно сгенерировать все возможные перестановки 1 и 0 для n испытаний Бернулли, но мне нужно сделать это по одному, чтобы все они генерировались, и ни одна не генерировалась более одного раза для произвольного n , Для n = 3, 2 ^ 3 = 8 я бы сначала сгенерировал

000

вычислить, была ли моя тестовая статистика больше (1 или 0), а затем сгенерировать

001

вычислить заново, затем сгенерировать

010

рассчитать, затем сгенерировать

100

вычислить, затем сгенерировать

011

и т. Д. До 111

Я согласен с тем, что это цикл более 2 ^ n, который выводит перестановку на каждом шаге цикла, но не сохраняет их где-либо. Кроме того, мне все равно, в каком порядке они генерируются. Выше перечислено, как я бы перечислил их, если бы делал это вручную.

Кроме того, если есть какой-либо способ ускорить предыдущий код, это также будет полезно.

Answer 1

Хорошее решение вашей проблемы - итераторы. Существует пакет под названием arrangements, который может генерировать перестановки итеративным способом. Обратите внимание:

library(arrangements)

# initialize iterator 
iperm <- ipermutations(0:1, 3, replace = T)

for (i in 1:(2^3)) {
    print(iperm$getnext())
}

[1] 0 0 0
[1] 0 0 1
.
.
.
[1] 1 1 1

Он написан на C и очень эффективен. Вы также можете генерировать m перестановок за один раз, например:

iperm$getnext(m)

Это позволяет повысить производительность, поскольку следующие перестановки генерируются циклом for в C, а не циклом for в R.

Если вам действительно нужно повысить производительность, вы можете воспользоваться пакетом parallel.

iperm <- ipermutations(0:1, 40, replace = T)

parallel::mclapply(1:100, function(x) {
    myPerms <- iperm$getnext(10000)
    # do something
}, mc.cores = parallel::detectCores() - 1)

Примечание. Весь код не проверен.