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

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

4 голосов
/ 05 августа 2011

Я пытаюсь найти все уникальные группировки вектора / списка элементов длиной 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))))

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

Ответы [ 2 ]

3 голосов
/ 05 августа 2011

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

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

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

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

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

0 голосов
/ 05 августа 2011

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

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

...