Найдите powerset всех уникальных комбинаций вектора строк

Я пытаюсь найти все уникальные группы вектора/списка элементов длиной 39. Ниже приведен код, который у меня есть:

x <- c("Dominion","progress","scarolina","tampa","tva","TminKTYS",
       "TmaxKTYS","TminKBNA","TmaxKBNA","TminKMEM","TmaxKMEM",
       "TminKCRW","TmaxKCRW","TminKROA","TmaxKROA","TminKCLT",
       "TmaxKCLT","TminKCHS","TmaxKCHS","TminKATL","TmaxKATL",
       "TminKCMH","TmaxKCMH","TminKJAX","TmaxKJAX","TminKLTH",
       "TmaxKLTH","TminKMCO","TmaxKMCO","TminKMIA","TmaxKMIA",
       "TminKPTA","TmaxKTPA","TminKPNS","TmaxKPNS","TminKLEX",
       "TmaxKLEX","TminKSDF","TmaxKSDF")

# Generate a list with the combinations  
zz <- sapply(seq_along(x), function(y) combn(x,y))
# Filter out all the duplicates
sapply(zz, function(z) t(unique(t(z))))

Однако код приводит к тому, что моему компьютеру не хватает памяти. Есть лучший способ сделать это? Я понимаю, что у меня большой список. благодаря.


r list unique combinations powerset
person HazelnutCoffee    schedule 05.08.2011    source источник
comment
ВСЕ группы (как и во всех подмножествах) или только все пары?   -  person Iterator    schedule 05.08.2011
comment
Эм....sum(choose(39,1:39)) = 549755813887. Подумайте на секунду о том, насколько велико это число, а теперь подумайте, действительно ли вы хотите это сделать.   -  person joran    schedule 05.08.2011
comment
@joran: Когда вы говорите, подумайте, насколько он велик ... вы имеете в виду, например: 549755813887 или ~ 549 миллиардов, это 1/25 долга США? ;-)   -  person Kyle Brandt    schedule 05.08.2011
comment
@RyanB, я понимаю, ты думаешь, что тебе нужны все комбинации... но я подозреваю, что на самом деле тебе не нужны все комбинации. Является ли это проблемой максимизации некоторого типа? Если это так, вы можете задать другой вопрос о том, как решить определенный тип поиска цели, а не перебор всех возможных комбинаций.   -  person JD Long    schedule 05.08.2011
comment
@Kyle Я больше думал о том, что ~ 549 миллиардов почти в 4 раза больше среднего расстояния от солнца до земли в метрах. Но твой тоже работает! ;)   -  person joran    schedule 05.08.2011
comment
549Б? Просто используйте mmap. Или Хадуп. :)   -  person Iterator    schedule 05.08.2011
comment
@joran: Некоторые люди используют sum(choose()), а некоторые просто вычисляют 2^39 - 1. :)   -  person Iterator    schedule 05.08.2011
comment
Чем это отличается от вашего предыдущего вопроса, R Question Количество уникальных комбинаций А,А,А,А,В,В,В,В,В?   -  person Joshua Ulrich    schedule 05.08.2011
comment
вовлеченный размер. отсюда вопрос Есть ли лучший способ сделать это?   -  person HazelnutCoffee    schedule 06.08.2011
comment
Размер N=39. Вам нужен набор мощности, то есть все 2 ^ 39 -1 возможных комбинаций всех возможных длин 1..N, а не только комбинации по две одновременно. Тег [power-set]   -  person smci    schedule 20.05.2018
comment
Это поможет, если вы покажете нам, почему вам это нужно, то есть покажете нам остальную часть конвейера после этого. Представление их в виде битовых полей длиной 39, вероятно, лучше, чем манипулирование списками/векторами строк произвольной длины. Если вы рассматриваете возможность членства в наборе для кластеризации, создания тепловых карт и т. д., для всего этого существуют известные библиотеки, написанные на C++. Это почти наверняка проблема XY. Расскажите нам о вашей реальной потребности.   -  person smci    schedule 20.05.2018

Ответы (2)


arrow_upward
3
arrow_downward

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

Поскольку имеется 39 элементов, и каждый из них может быть как в данном подмножестве, так и не в нем, то существует 2^39 возможных подмножеств. За исключением пустого набора, то есть вектора со всеми 0, у вас есть 2 ^ 39 - 1 возможных подмножеств.

То есть, как сказал @joran, около 549B векторов. Учитывая, что двоичные векторы наиболее компактно представляют данные (т.е. без строк), вам потребуется 549B * 39 бит, чтобы вернуть все подмножества. Я не думаю, что вы хотите хранить это: это около 2,68E12 байт. Если вы настаиваете на использовании символов, вы, вероятно, получите много десятков терабайт.

Конечно, можно купить систему, которая может поддерживать это, но не очень рентабельно.

На мета-уровне очень вероятно, как сказал @JD, что это не тот путь, по которому вам действительно нужно идти. Я рекомендую опубликовать новый вопрос, и, возможно, его можно уточнить здесь или на сайте SE, связанном со статистикой.

person Iterator    schedule 05.08.2011
comment
FWIW, даже если вы не сохраните его, передача данных займет некоторое время. Любой приличный компьютер должен очень быстро генерировать все 39-битные векторы. См. Взломщик паролей грубой силы для иллюстративных целей. :) DES был 56-битным ключом, поэтому немного длиннее, и требовалось несколько больше вычислений для каждого ключа. - person Iterator; 05.08.2011

arrow_upward
0
arrow_downward

Вы можете попробовать использовать expand.grid.

Создайте фрейм данных из всех комбинаций предоставленных векторов или факторов. Подробные сведения о том, как это делается, см. в описании возвращаемого значения.

person Kyle Brandt    schedule 05.08.2011
comment
Это не будет красиво - я надеюсь, что OP и много времени в их руках, огромный стек оперативной памяти и достаточно терпения, чтобы прополоть полученные комбинации ... - person Gavin Simpson; 05.08.2011
comment
@Gavin: Согласен, просто оставлю это здесь на случай, если это поможет будущему человеку с меньшим набором факторов. - person Kyle Brandt; 05.08.2011
comment
я ищу все уникальные подмножества. это действительно в миллиардах? - person HazelnutCoffee; 05.08.2011
comment
@RyanB: Итак, все это подпадает под базовую комбинаторику. Возникает несколько основных вопросов: Мне важен порядок. Хочу ли я знать все комбинации, включающие все элементы, или все комбинации из 5 из набора из 20? Подобные вещи значительно меняют размер результата. Это, вероятно, займет у вас час, чтобы получить основы книги с вероятностью для чайников, и это будет стоить вашего времени. - person Kyle Brandt; 05.08.2011
comment
Вы тот же Кайл Брандт, который уничтожает SO (blog.serverfault .com/post/)? Пожалуйста, сообщите нам, что вы не собираетесь запускать это на серверах SO. ;-) - person Iterator; 05.08.2011