Я пытаюсь показать сыну, как можно использовать кодирование для решения проблемы, возникающей в игре, а также посмотреть, как R обрабатывает большие данные. Эта игра называется «Счастливчик 26». В этой игре числа (1-12 без дубликатов) расположены на 12 точках звезды Давида (6 вершин, 6 пересечений), и 6 линий по 4 числа должны все добавить к 26. Из приблизительно 479 миллионов возможностей (12P12 ) есть, по-видимому, 144 решения. Я попытался закодировать это в R следующим образом, но, похоже, проблема с памятью. Я был бы очень признателен за любой совет, если у участников будет время. Поблагодарив членов заранее.
library(gtools)
x=c()
elements <- 12
for (i in 1:elements)
{
x[i]<-i
}
soln=c()
y<-permutations(n=elements,r=elements,v=x)
j<-nrow(y)
for (i in 1:j)
{
L1 <- y[i,1] + y[i,3] + y[i,6] + y[i,8]
L2 <- y[i,1] + y[i,4] + y[i,7] + y[i,11]
L3 <- y[i,8] + y[i,9] + y[i,10] + y[i,11]
L4 <- y[i,2] + y[i,3] + y[i,4] + y[i,5]
L5 <- y[i,2] + y[i,6] + y[i,9] + y[i,12]
L6 <- y[i,5] + y[i,7] + y[i,10] + y[i,12]
soln[i] <- (L1 == 26)&(L2 == 26)&(L3 == 26)&(L4 == 26)&(L5 == 26)&(L6 == 26)
}
z<-which(soln)
z
r
bigdata
permutation
DesertProject
источник
источник
x<- 1:elements
и что более важноL1 <- y[,1] + y[,3] + y[,6] + y[,8]
. Это не поможет вашей проблеме с памятью, поэтому вы всегда можете посмотреть в rcpprm(list=ls())
вставляйте свой MRE. Если кто-то копирует и вставляет в активный сеанс, он может потерять свои собственные данные.Ответы:
Вот другой подход. Он основан на пост MathWorks блоге по Клив Moler , автор первой MATLAB.
В сообщении в блоге для экономии памяти автор переставляет только 10 элементов, оставляя первый элемент в качестве элемента apex и 7-й в качестве базового элемента. Поэтому только
10! == 3628800
перестановки должны быть проверены.В приведенном ниже коде
1
для10
. Всего10! == 3628800
их есть.11
как верхний элемент и сохраните его фиксированным. Это действительно не имеет значения, где начинаются назначения, другие элементы будут в правильном отношении позициях.for
цикле.Это должно дать большинство решений, дать или взять повороты и отражения. Но это не гарантирует, что решения уникальны. Это также достаточно быстро.
источник
На самом деле существует 960 решений. Ниже мы используем
Rcpp
,RcppAlgos
* иparallel
пакет, чтобы получить решение чуть более,6 seconds
используя 4 ядра. Даже если вы решите использовать однопоточный подход с базой Rlapply
, решение возвращается примерно через 25 секунд.Сначала мы напишем простой алгоритм,
C++
который проверяет конкретную перестановку. Вы заметите, что мы используем один массив для хранения всех шести строк. Это для производительности, так как мы используем кэш-память более эффективно, чем 6 отдельных массивов. Вы также должны иметь в виду, чтоC++
используется индексация с нуля.Теперь, используя аргументы
lower
и , мы можем генерировать порции перестановок и тестировать их по отдельности, чтобы контролировать память. Ниже я выбрал для тестирования около 4,7 миллионов перестановок одновременно. Выходные данные дают лексикографические показатели перестановок 12! так что условие Lucky 26 выполнено.upper
permuteGeneral
Теперь мы проверяем использование
permuteSample
и аргумент,sampleVec
который позволяет вам генерировать конкретные перестановки (например, если вы передадите 1, он даст вам первую перестановку (т.е.1:12
)).Наконец, мы проверяем наше решение с базой R
rowSums
:* Я автор
RcppAlgos
источник
Для перестановок rcppalgos отлично подходит. К сожалению, существует 479 миллионов возможностей с 12 полями, что означает, что для большинства людей это занимает слишком много памяти:
Есть несколько альтернатив.
Возьмите образец перестановок. То есть только 1 миллион вместо 479 миллионов. Для этого вы можете использовать
permuteSample(12, 12, n = 1e6)
. См. Ответ @ JosephWood о похожем подходе, за исключением того, что он выбрал 479 миллионов перестановок;)Создайте цикл в rcpp для оценки перестановки при создании. Это экономит память, потому что вы в конечном итоге создадите функцию, которая будет возвращать только правильные результаты.
Подход к задаче с другим алгоритмом. Я сосредоточусь на этом варианте.
Новый алгоритм с ограничениями
Сегментов должно быть 26
Мы знаем, что каждый сегмент линии в звезде выше должен добавить до 26. Мы можем добавить это ограничение к генерации наших перестановок - дать нам только комбинации, которые в сумме дают 26:
ABCD и EFGH группы
В приведенной выше звезде я по-разному раскрасил три группы: ABCD , EFGH и IJLK . Первые две группы также не имеют общих точек и также представляют интерес на линейных отрезках. Поэтому мы можем добавить еще одно ограничение: для комбинаций, которые в сумме составляют 26, мы должны убедиться, что ABCD и EFGH не перекрываются. IJLK будет присвоен оставшиеся 4 номера.
Переставить через группы
Нам нужно найти все перестановки каждой группы. То есть у нас есть только комбинации, которые в сумме составляют 26. Например, нам нужно взять
1, 2, 11, 12
и сделать1, 2, 12, 11; 1, 12, 2, 11; ...
.Окончательные расчеты
Последний шаг - сделать математику. Я использую
lapply()
иReduce()
здесь, чтобы сделать более функциональное программирование - в противном случае много кода было бы напечатано шесть раз. Смотрите оригинальное решение для более подробного объяснения математического кода.Перекачка ABCD и EFGH
В конце кода выше я воспользовался тем, что мы можем поменяться местами
ABCD
иEFGH
получить оставшиеся перестановки. Вот код, подтверждающий, что да, мы можем поменять две группы и быть правильными:Представление
В итоге мы оценили только 1,3 миллиона из 479 перестановок и только перетасовали только 550 МБ ОЗУ. Для запуска требуется около 0,7 с
источник
Вот решение для маленького парня:
источник