Вопросы с тегами [combinations]

536

голосов
30

ответ
416.4k

Просмотры

Алгоритм для возврата всех комбинаций к элементам из п

Я хочу, чтобы написать функцию, которая принимает массив букв в качестве аргумента и ряда этих писем для выбора. Скажем, вы предоставляете массив 8 букв и хотите выбрать 3 письма от этого. Тогда вы должны получить: 8! / ((8 - 3) * 3!) = 56 Массивы (или слова) взамен состоящие из 3-х букв в каждой.
282

голосов
23

ответ
427.1k

Просмотры

Как получить все возможные комбинации элементов списка в?

У меня есть список с 15 номеров в, и мне нужно написать код, который производит все 32768 комбинаций этих чисел. Я нашел некоторый код (по погуглить), что, видимо, делает то, что я ищу, но я нашел код достаточно непрозрачным, и я настороженно относятся к его использования. Плюс у меня есть ощущение, что должно быть более элегантное решение. Единственное, что происходит со мной, было бы просто перебрать десятичных чисел 1-32768 и преобразовать те в двоичный формат и использовать бинарное представление в качестве фильтра, чтобы выбрать соответствующие номера. Кто-нибудь знает лучший способ? Использование карты (), может быть?
Ben
190

голосов
25

ответ
298k

Просмотры

Нахождение всех возможных комбинаций чисел для достижения заданной суммы

Как бы вы о тестировании всех возможных комбинаций добавок из заданного набора чисел так, что они добавляют до заданного конечного числа? Пример: Набор чисел, чтобы добавить: {1,5,22,15,0, ...} Желаемый результат: 12345
James P.
168

голосов
5

ответ
80.9k

Просмотры

Все комбинации списка списков

Я в основном ищу версию питона совмещения Списка Учитывая список списков, мне нужен новый список, который дает все возможные комбинации элементов между списками. [[1,2,3], [4,5,6], [7,8,9,10]] -> [[1,4,7], [1,4,8], ..., [3,6,10]] число списков неизвестно, так что мне нужно что-то, что работает для всех случаев. Бонусные баллы за элегантность!
Lin
104

голосов
15

ответ
397.7k

Просмотры

Как объединить две строки вместе в PHP?

Я на самом деле не знаю, как описать то, что я хотел, но я покажу вам, например: $ data1 = «цвет»; $ Data2 = "красный"; Что я должен делать (или процесс), так что $ результатом является сочетание $ data1 и $ data2? Желаемый результат: $ результат = «цвет красный»;
glennanyway
97

голосов
14

ответ
89.2k

Просмотры

Статистика: комбинации в Python

Мне нужно вычислить combinatorials (NCR) в Python, но не может найти функцию, чтобы сделать это в математике, Numpy или стат библиотек. Что-то вроде функции типа: расческа = calculate_combinations (п, г) мне нужно число возможных комбинаций, а не фактических комбинаций, так itertools.combinations меня не интересует. Наконец, я хочу, чтобы избежать использования факториалов, как номер я буду расчетом комбинаций для могут получить слишком большими и факториалы будут чудовищными. Это кажется очень легко ответить на вопрос, однако я утонуть в вопросах о генерации всех реальных комбинаций, которые не то, что я хочу. :) Большое спасибо
Morlock
85

голосов
12

ответ
10.8k

Просмотры

Быстрее альтернатива вложенных циклов?

У меня есть необходимость создать список комбинаций чисел. Номера довольно маленькие, так что я могу использовать байты, а не междунар. Однако это требует много вложенных циклов, чтобы получить все возможные комбинации. Я интересно, если есть более эффективный способ, чтобы сделать то, что я после. Код до сих пор: вар данные = новый список (); для (байт а = 0; а <2; A ++) для (BYTE B = 0, б <3, б ++), для (байт с = 0; с <4; C ++) для (байт d = 0; д <3; d ++), для (байт е = 0; е <4; е ++), для (байт F = 0, е <3, е ++), для (байт г = 0; г <3; г ++), для (байт Н = 0, H < 4; ч ++), для (байт = 0; г <2; я ++), для (байт J = 0; J <4; j ++) для (байт к = 0; к <4; K ++), для (байт л = 0; л <3; л ++), для (байт т = 0, т <4; M ++) {data.Add (новый [] {а, б, в, г, д, е, ж, з, I, J, K, л, м}); } Я рассматривал, используя что-то вроде BitArray, но я не знаю, как я мог включить его. Любые рекомендации будут весьма благодарны. С другой стороны, возможно, это самый быстрый способ сделать то, что я хочу? EDIT Пара быстрых точек (и извинений я не ставил их в исходном сообщении): Числа и порядок их (2, 3, 4, 3, 4, 3, 3 и т.д.) очень важны, так что с помощью решение таких как генерация Перестановка с использованием LINQ не поможет, потому что максимумы в каждом «столбце» отличаются я не математиком, поэтому я прошу прощения, если я не использую технические термины, как «перестановки» и правильно «комбинация»: ) Мне нужно, чтобы заполнить все эти комбинации сразу - я не могу просто взять один или другой на основе индекса Использование байт быстрее, чем при использовании Int, я гарантирую это. Это' S также намного лучше на использование памяти, чтобы иметь 67M + массивы байтов, а не INTS Моей конечной целью здесь является поиск более быстрой альтернативой вложенных циклов. Я рассматривал параллельное программирование, но из-за итеративный характер того, что я пытаюсь достичь, я не мог найти способ сделать это успешно (даже с ConcurrentBag) - однако я рад быть опровергнуты :) ВЫВОД Caramiriel обеспечила хороший микро-оптимизации, которая бреет некоторое время выключения петли, поэтому я пометил этот ответ как правильный. Эрик также отметил, что это быстрее, предварительно выделить список. Но на данном этапе, кажется, что вложенные циклы, на самом деле самый быстрый способ сделать это (угнетает, я знаю!). Если вы хотите попробовать именно то, что я пытался бенчмарка с секундомером, идти с 13 циклов подсчета до 4 в каждой петле - что составляет около 67m + строки в списке. На моей машине (i5-3320M 2.6GHz) она занимает около 2.2s делать оптимизированную версию.
benpage
64

голосов
3

ответ
22.3k

Просмотры

Сочетание двух массивов в Ruby,

Каков путь рубин достичь следующего? а = [1,2] Ь = [3,4] Я хочу массив: => [F (1,3), F (1,4), F (2,3), F (2,4)]
pierrotlefou
52

голосов
11

ответ
39.8k

Просмотры

Генерация всех двоичных строк длины п с множеством К бит

Какой лучший алгоритм для поиска всех двоичных строк длины п, которые содержат биты K установить? Например, если п = 4 и к = 3, есть ... 0111 1011 1101 1110 Мне нужен хороший способ, чтобы генерировать эти данные любого п и любого к, так что я бы предпочел, чтобы это было сделано со строками.
kevmo314
51

голосов
6

ответ
55.6k

Просмотры

Захватив Ctrl + комбинация г ключ в JavaScript

Я пытаюсь захватить Ctrl + комбинацию клавиш г в JavaScript с помощью этого кода: Untitled функция Document KeyPress (е) {вар evtobj = window.event? Событие: д // test1, если (evtobj.ctrlKey) предупреждение ( "Ctrl"); // test2 если (evtobj.keyCode == 122) предупреждение ( "г"); // Тест 1 & 2, если (evtobj.keyCode == 122 && evtobj.ctrlKey) предупреждение ( "Ctrl + Z"); } Document.onkeypress = KeyPress; Ответил линия «test1» генерирует предупреждение, если я, удерживая клавишу CTRL и нажмите любую другую клавишу. Ответил линия «test2» генерирует предупреждение, если нажать клавишу г. Поместите их вместе, как на линии после того, как «тест 1 & 2», и, удерживая нажатой клавишу CTRL, то нажатие на клавишу г не вызывает тревогу, как и ожидалось.
Paul Johnston
50

голосов
4

ответ
15.2k

Просмотры

Создает матрицу, содержащую все комбинации элементов, взятых из п векторов

Этот вопрос всплывает довольно часто в той или иной форме (см, например, здесь или здесь). Так я думал, что представить его в общем виде, и дать ответ, который мог бы служить для дальнейшего использования. Принимая во внимание произвольное число п векторов, возможно, различных размеров, генерировать матрицу п-столбца, строки которой описаны все комбинации элементов, взятых из этих векторов (декартово произведение). Например, векторы = {[1 2], [3 6 9], [10 20]} должны дать расчески = [1-10 1-20 1-10 1-20 1-10 1-20 2-10 2 3 20 2-10 2-20 2-10 2-20]
Luis Mendo
49

голосов
11

ответ
71.6k

Просмотры

Генерирование комбинации в C ++

Я искал исходный код для создания комбинации с использованием C ++. Я нашел некоторые дополнительные коды для этого, но это хорошо только для конкретных числовых данных предопределены. Может кто-нибудь дать мне несколько советов, или, возможно, некоторые идеи для создания комбинации. В качестве примера, предположим, что множество S = {1, 2, 3, ...., N}, и мы выбираем г = 2 из него. Вход будет п и r.In этот случай, программа будет генерировать массивы длины два, как 5 2 выходов 1 2, 1 3, и т.д .. У меня были трудности при построении алгоритма. Он взял меня в месяц думать об этом.
Keneth Adrian
44

голосов
7

ответ
48.6k

Просмотры

Как создать все пары из двух векторов в MATLAB, используя vectorised код?

Не раз сейчас я необходимо сгенерировать все возможные пары двух векторов в MATLAB, которые я делаю с петлями для которых занимают справедливые несколько строк кода, т.е. vec1 = 1: 4; vec2 = 1: 3; I = 0; пар = нули ([4 * 3 2]); для знач1 = vec1 для знач2 = vec2 I = I + 1; пары (я, 1) = знач1; пары (я, 2) = знач2; конец конец Формирует ... 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 4 1 4 2 4 3 Там должен быть лучший способ сделать это, которое более MATLAB'esque? нб nchoosek не делать обращенные пары, что мне нужно (т.е. 2 1, а также 1 2), я не могу просто развернуться и добавьте nchoosek выход, так как симметричные пары будут включены в два раза.
Brendan
43

голосов
8

ответ
22.2k

Просмотры

JavaScript - Генерирование комбинации из п массивов с т элементов

У меня возникли проблемы придумать код для создания комбинации из п числа массивов с м числом элементов в них, в JavaScript. Я видел подобные вопросы об этом на других языках, но ответы включают синтаксическую или библиотеку магию, что я не уверен, как перевести. Рассмотрим эти данные: [[0,1], [0,1,2,3], [0,1,2]] 3 массивы, с различным числом элементов в них. То, что я хочу сделать, это получить все комбинации, комбинируя элемент из каждого массива. Например: 0,0,0 // элемента массива 0 от 0, 0 от элемента массива 1, п 0 из массива 0,0,1 0,0,2 2 0,1,0 0,1,1 0,1 , 2 0,2,0 0,2,1 0,2,2 и так далее. Если число массивов фиксировалось, было бы легко сделать трудно закодированную реализацию. Но количество массивов может изменяться: [[0,1], [0,1]] [[0,1,3,4], [0,1], [0], [0,1]] Любая помощь была бы оценена.
quano
38

голосов
5

ответ
11k

Просмотры

Path.Combine и точечная нотация [дубликат]

Этот вопрос уже есть ответ здесь: Path.Combine абсолютная с относительными путем строками 5 ответов я ищу что-то сродни методу Path.Combine, который поможет мне правильно сочетать абсолютные и относительные пути. Например, я хочу Path.Combine (@ "C: \ альфа \ бета", @ ".. \ гамма"); с получением C: \ альфа \ гамма вместо C: \ альфа \ .. \ гамма как это делает Path.Combine. Есть ли простой способ достичь этого? Само собой разумеется, я тоже хочу период. путь или несколько .. путей (например, .. \ .. \), чтобы работать правильно.
Dmitri Nesteruk
36

голосов
7

ответ
2.3k

Просмотры

Найти все комбинации 3х3 holepunch

I was at a carnival where at each location they mark your program with a special hole punch. The hole punch is a grid of 3x3 spaces. In each space, there's either a pin that punctures your paper or there isn't. This got me to wondering how many different patterns you could make with this tool. My first thought was: 2^9 = 512, but all 9 spaces being pinless isn't really a punch, so really: 511. Then the complexity hit me. Especially since the workers aren't all that careful when they punch your paper, these would all look idential: x.. .x. ... etc. .x. x.. .x. ... ... ..x Question: How could a test be written to account for rotation and shifting? Diligence and thoughts so far: Binary feels like an obvious part of this equation When a unique pattern is found, store it in memory so future patterns can be tested against it There are 4 rotation possibilities.Edit: what I mean by "rotations" is that you can take any shape and turn it 90 degrees. Consider the pattern that is a dot in the upper left corner. You can turn/rotate it 90 degrees and get the dot in the upper right corner. Do this again and it's in the lower right. Again and it's in the lower left. Using the pure 2^9 calculation, these are 4 different combinations. For this problem however, these are exactly the kind of duplicates I'm trying to weed out. For each rotation, there are 25 ways to make 3x3 grids overlap: Overlaps: / = the spaces in the new one to test \ = the spaces in a verified unique one 1 2 25 / / / . . . . . / / / . . . . . . . . . . / / / . . . . . / / / . . . . . . . . . . / / X \ \ . . . / X X \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ \ . . . . \ \ X / / . . . . . . . . . . . . . . . . . . / / / . . . . . . . . . . . . . . . . . . / / / An overlap doesn't need to be tested if either pattern contains a pin that isn't in the overlap area. Bitwise AND could help here. If you make each position for each of the 2 patterns into strings, you can just check for equality Can these previous two ideas be combined to increase efficiency?
Dinah
35

голосов
4

ответ
26.3k

Просмотры

Как создать все перестановки строки в PHP?

Мне нужен алгоритм, вернуть все возможные комбинации всех символов в одной строке. Я пробовал: $ langd = StrLen ($ вход); для ($ I = 0; $ г <$ langd; $ я ++) {$ tempStrang = NULL; $ TempStrang = зиЬзЬги ($ ввод, $ я, 1). для ($ J = $ + 1, $ к = 0; $ к <$ langd; $ K ++ $ j ++) {если ($ J> $ langd) $ J = 0; $ TempStrang = зиЬзЬг ($ ввода, $ J, 1). } $ MyArray [] = $ tempStrang; } Но это только возвращает ту же самую комбинацию суммы в качестве длины строки. Произнесите $ вход = "эй", результат будет: эй, Хе, EYH, EHY, Yhe, Yeh.
Johan
35

голосов
5

ответ
58k

Просмотры

Выполнение всех возможных комбинаций списка

Мне нужно, чтобы быть в состоянии сделать список, содержащий все возможные комбинации введенного списка. Например, список [1,2,3] должна возвращать [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] Список не должен быть в любом определенный порядок. На этом сайте я нашел много функций, используя itertools но те возвращаются объекты, когда мне нужно просто список.
Charles
34

голосов
5

ответ
32.1k

Просмотры

Сформировать список всех возможных комбинаций элементов вектора

Я пытаюсь создать все возможные комбинации 0 и 1-е в векторе длина 14. Есть простой способ получить этот вывод в виде списка векторов, или даже лучше, dataframe? Для того, чтобы продемонстрировать, что лучше я ищу, давайте предположим, что я хочу только вектор длины 3. Я хотел бы быть в состоянии произвести следующие действия: (1,1,1), (0,0,0), (1 , 1,0), (1,0,0), (1,0,1), (0,1,0), (0,1,1), (0,0,0) Любая помощь будет признателен ! Спасибо,
Mayou
33

голосов
11

ответ
33k

Просмотры

counting combinations and permutations efficiently

У меня есть некоторый код для подсчета перестановок и комбинаций, и я стараюсь, чтобы заставить его работать лучше для больших чисел. Я нашел лучший алгоритм для перестановок, которые позволяют избежать больших промежуточных результатов, но я до сих пор думаю, что я могу сделать лучше для комбинаций. До сих пор, я поместил в особом случае, чтобы отразить симметрию Ncr, но я все еще хотел бы найти лучший алгоритм, который позволяет обойтись без вызова Факториала (г), которая является излишне большим промежуточным результатом. Без этой оптимизации, последний doctest занимает слишком много времени, пытаясь вычислить факториал (99000). Можно ли предложить более эффективный способ подсчета комбинаций? от импорта математики факторного четкости продукта (итерация): прод = 1 для п в Iterable: прод * = п возврата Prod Защиты NPR (п, г): ""» Расчет числа упорядоченных перестановок элементов г, взятые из популяции размера п. >>> NPR (3, 2) 6 >>> NPR (100, 20) 1303995018204712451095685346159820800000 ""»утверждают 0
Christian Oudard
33

голосов
7

ответ
13.7k

Просмотры

Алгоритм выбора одного, случайное сочетание значений?

Скажем, у меня есть Y различных значений, и я хочу, чтобы выбрать х из них случайным образом. Что такое эффективный алгоритм для этого? Я мог бы просто позвонить рандов () х раз, но производительность будет низкой, если х, у, были велики. Обратите внимание, что здесь необходимы комбинации: каждое значение должно иметь ту же вероятность быть выбрана, но их порядок в результате не важен. Конечно, любая порождающий алгоритм перестановка будет иметь право, но мне интересно, если это возможно, чтобы более эффективно делать это без требования в случайном порядке. Как вы эффективно генерировать список K неповторяющихся чисел между 0 и верхней границей N охватывает этот случай перестановок.
32

голосов
8

ответ
94.6k

Просмотры

Создание всех возможных комбинаций к из п элементов в C ++

Есть русские люди, пронумерованных от 1 до п. Я должен написать код, который производит и напечатать все различные комбинации из к людям из этого п. Объясните, пожалуйста, алгоритм, используемый для этого.
Prannoy Mittal
32

голосов
5

ответ
25.5k

Просмотры

Как создать в PHP все комбинации элементов в нескольких массивов

I'im пытается найти все сочетания элементов в нескольких массивах. Количество массивов случайным образом (это может быть 2, 3, 4, 5 ...). Количество элементов в каждом массиве является случайным тоже ... Для Exemple, у меня есть 3 массива: $ Arraya = массив ( «A1», «A2», «A3»); $ ArrayB = массив ( 'В1', 'В2', 'В3'); $ ArrayC = массив ( '1', 'С2'); Я хотел бы, чтобы генерировать массив с 3 х 3 х 2 = 18 комбинаций: A1, B1, C1-А1, В1, С2 А1, В2, С1 А1, В2, С2 А1, В3, C1-A1, B3, C2-A2, B1 , C1-А2, В1, С2 ... проблема заключается в том, чтобы создать функцию с переменным числом исходных массивов ...
Yohan
32

голосов
10

ответ
889

Просмотры

Алгоритм определения всех возможных путей группы значений могут быть удалены из последовательности

Я пытаюсь определить, сколько различных способов, которыми я могу удалить группу значений из последовательности, оставляя исходную последовательность в порядке (стабильный), и убедившись, чтобы удалить только 1 значение экземпляра каждого из исходной последовательности. Например, если бы я был [1,2,1,3,1,4,4] и я хочу, чтобы удалить [1,4,4] мои результате комбинации будут: [1,2,1,3,1, 4,4] \ [1,4,4] = [[2,1,3,1], [1,2,3,1], [1,2,1,3]] или [1,2, 1,3,1,4,4] \ [1,1] = [[2,3,1,4,4], [1,2,3,4,4], [2,1,3,4 , 4]] у меня есть яваскрипт кода, который я написал для создания комбинаций всех значений массива без удаления и часть удаления кажется, что это должно быть легко, но я не вижу алгоритм при необходимости потенциально удалить несколько значений несколько раз.
bkaid
31

голосов
11

ответ
39.3k

Просмотры

Как эффективно вычислить строку в треугольнике Паскаля?

Я заинтересован в поиске п-й ряд треугольника Паскаля (не конкретный элемент, но сам всю строку). Что было бы наиболее эффективный способ сделать это? Я подумал о обычном способе, чтобы построить треугольник пути суммирования соответствующих элементов в строке, над которой будет выполняться: 1 + 2 + .. + п = O (N ^ 2) Другим способ может быть с помощью комбинации формулы конкретного элемент: с (п, к) = п! / (К! (Пк)!) Для каждого элемента в строке, которую я предполагаю бы больше времени первого метода в зависимости от способа расчета комбинации. Есть идеи?
none
31

голосов
1

ответ
769

Просмотры

Is `scipy.misc.comb` faster than an ad-hoc binomial computation?

Is it conclusive that now the scipy.misc.comb is indeed faster than the ad-hoc implementation? According to an old answer, Statistics: combinations in Python, this homebrew function is faster than scipy.misc.comb when calculating combinations nCr: def choose(n, k): """ A fast way to calculate binomial coefficients by Andrew Dalke (contrib). """ if 0
alvas
31

голосов
8

ответ
41.3k

Просмотры

Вычислить значение п выбрать к [закрытыми]

Что является наиболее эффективным методом для оценки значения п выбрать к? Перебор, как я думаю, что было бы найти п / к факторному факторному / (пк) факториал. Лучшая стратегия может быть использование дпа согласно этой рекурсивной формуле. Есть ли другой метод лучше оценить п выбрать к?
Nikunj Banka
30

голосов
11

ответ
57.1k

Просмотры

Все возможные комбинации списка значений

У меня есть список целых чисел в моей C # программы. Тем не менее, я знаю, что количество элементов у меня есть в моем списке только во время выполнения. Скажем, для простоты, мой список {1, 2, 3} Теперь мне нужно сгенерировать все возможные комбинации следующим образом. {1, 2, 3} {1, 2} {1, 3} {2, 3} {1} {2} {3} Может кто-нибудь, пожалуйста, помогите с этим?
Sach
28

голосов
5

ответ
7.9k

Просмотры

Нерезервированная версия expand.grid

Функция R expand.grid возвращает все возможные комбинации между элементами поставляемых параметров. например> expand.grid (с ( "аа", "б", "CC"), с ( "аа", "б", "CC")) Var1 Переменная2 1 аа аа аа 2 аб 3 сс аа аа 4 аб 5 аб абы 6 куб.сма абы 7 аа сс 8 абы куб.см 9 куб.см куб.сма вы знаете эффективный способ получить непосредственно (так без какого-либо сравнения строк после expand.grid) только «уникальная» комбинацию между прилагаемыми векторами ли? Выход будет Var1 Переменная2 1 аа аа аа 2 аб 3 сс аа 5 AB AB 6 куб.см AB 9 куб.см куб.см РЕДАКТИРОВАТЬ сочетание каждого элемента с самим собой может быть в конечном итоге отбрасываются от ответа. Я не» т на самом деле нужен в моей программе, даже если (математически) аа аа будет один (регулярное) Уникальное сочетание между одним элементом Var1 и другим var2. Решение должно производить пар элементов из обоих векторов (то есть по одному от каждого из входных векторов - так, чтобы он мог быть применен к более чем 2 входами)
Michele
27

голосов
3

ответ
7k

Просмотры

Объединить массив массива во все возможные комбинации, только вперед, в Рубине

У меня есть массив массивов, например, так: [[ «1», «2»], [ «а», «Ь»], [ «х», «у»]] мне нужно объединить эти массивы в строку содержащий все возможные комбинации всех трех наборов, только вперед. Я видел много примеров всех возможных комбинаций множеств в произвольном порядке, то есть не то, что я хочу. Например, я не хочу какой-либо из элементов в первом наборе прийти после второго набора, или любой в третьем сете прийти перед первым или вторым, и так далее. Таким образом, для приведенного выше примера, то выход будет: [ '1AX', '1AY', '1BX', '1by', '2', '2AY', '2BX', '2by'] Количество массивов, и длина каждого набора является динамической. Кто-нибудь знает, как решить эту проблему в Ruby?
Travis
26

голосов
3

ответ
28.3k

Просмотры

РНР алгоритм для генерации всех комбинаций определенного размера из одного набора

Я пытаюсь вывести алгоритм, который генерирует все возможные комбинации определенного размера что-то вроде функции, которая принимает массив символов и размер в качестве параметра и возвращать массив комбинаций. Пример: Допустим, что мы имеем набор символов: набор А = {A, B, C}, а) все возможные комбинации размера 2: (3 ^ 2 = 9) АА, АВ, АС ВА, ВВ, ВС СА, СВ , CC б) Все возможные комбинации размера 3: (3 ^ 3 = 27) AAA, AAB, AAC, ABA, ABB, ACC, CAA, BAA, BAC, .... объявление так далее общих комбинаций = 27 Обратите внимание, что размер пара может быть больше, чем общий размер pouplation. Ex. если набор содержит 3-х символов, то мы также можем создать комбинацию размера 4. EDIT: Кроме того, обратите внимание, что это отличается от перестановки. В перестановке мы не можем повторять символы для примера АА не может прийти, если мы используем алгоритм перестановки. В статистике известно как выборка.
asim-ishaq
25

голосов
7

ответ
25.3k

Просмотры

Java - Генерирование силового набора данного списка

Я пытаюсь создать коллекцию всех 2 ^ N - 1 возможных комбинации данного списка длиной N. Коллекция будет отображать количество элементов в сочетании с упорядоченным списком комбинаций, содержащей комбинацию конкретной длиной. Например, для списка: [А, В, С, D] Я хочу, чтобы создать карту: {1 -> [{A}, {B}, {C}, {D}] 2 -> [{A , B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}] 3 -> [{A, B, C}, {A, B , D}, {А, с, D}, {B, C, D}] 4 -> [{А, в, с, D}]} Сгенерированный база данных должна поддерживать исходный порядок (где [] представляет собой упорядоченную ряд (Список), и {} представляет собой не-упорядоченной группу (Set)), и работать так же быстро, как это возможно. Я боролся с каким-то рекурсивным кодом весь день (я знаю, что реализация должна быть рекурсивной), но не смог добраться до сути. Есть ли ссылка, которую я могу использовать / готовую реализацию такого алгоритма? UPDATE: Благодаря предыдущим ответам, я придумал следующую реализацию: общественного класса OrderedPowerSet {частный статический окончательный ИНТ ELEMENT_LIMIT = 12; частный Список inputList; общественности Int N; частная карта Карта = новый HashMap (); общественный OrderedPowerSet (список List) {inputList = список; N = list.size (); если (N> ELEMENT_LIMIT) {проливают новый RuntimeException ( "Список с более чем" + ELEMENT_LIMIT + "элементов слишком долго ..."); }} Общественного Список getPermutationsList (интермедиат ElementCount) {если (ElementCount <1 || ElementCount> N) {певд IndexOutOfBoundsException ( " getPermutationsList (ElementCount-1); (для LinkedHashSet S: Plist) {LinkedHashSet установлен = новый LinkedHashSet (); Set.add (inputList.get (я)); set.addAll (ы); list.add (комплект); }}} Map.put (ElementCount, список); вернуть map.get (ElementCount); }} Я был бы рад получить обратную связь для способов, чтобы улучшить это. UPDATE 2: Я установил несколько проблем в коде и тестировал. положим (ElementCount, список); вернуть map.get (ElementCount); }} Я был бы рад получить обратную связь для способов, чтобы улучшить это. UPDATE 2: Я установил несколько проблем в коде и тестировал. положим (ElementCount, список); вернуть map.get (ElementCount); }} Я был бы рад получить обратную связь для способов, чтобы улучшить это. UPDATE 2: Я установил несколько проблем в коде и тестировал.
Elist
24

голосов
7

ответ
20k

Просмотры

Сочетание List

Я список этого типа List>, содержащие этот список A = новый список {1, 2, 3, 4, 5}; Список B = новый список {0, 1}; Список С = новый список {6}; Список X = новый список {...., ....}; Я хочу, чтобы все комбинации, как этот 1-0-6 1-1-6 2-0-6 2-1-6 3-0-6 и так далее. По вами Это possibile разрешить с помощью Linq?
Giomuti
24

голосов
4

ответ
4.9k

Просмотры

Комбинации из словаря со значениями списка с помощью Python

У меня есть следующие входящие значения: варианты = { "отлаживать": [ "на", "выключено"], "локаль": [ "de_DE", "en_US", "fr_FR"], ...} Я хочу обработать их таким образом я получаю следующий результат: комбинации = [[{ "отлаживать": "на"}, { "локаль": "de_de"}], [{ "отлаживать": "на"}, { "локаль":» en_US "}], [{" отлаживать ":" на "}, {" локаль ":" fr_FR "}], [{" отлаживать ":" выкл "}, {" локаль ":" de_de "}], [ { "отлаживать": "выкл"}, { "локаль": "en_US"}], [{ "отлаживать": "выключено"}, { "локаль": "fr_FR"}]] Это должно работать с произвольной длиной ключи в словаре. Играл с itertools в Python,
Sebastian Werner
23

голосов
3

ответ
51.8k

Просмотры

Алгоритм, чтобы получить все комбинации размера п из массива (Java)? [закрыто]

Сейчас я пытаюсь написать функцию, которая принимает массив и целое число п, и дает список каждого размера п комбинации (так список Int массивов). Я могу написать его с помощью п вложенных циклов, но это работает только для определенного размера подмножества. Я не могу понять, как обобщить его на работу для любого размера комбинации. Я думаю, что нужно использовать рекурсию? Это код для всех комбинаций из 3 элементов, и мне нужно алгоритм для любого числа элементов. импорт java.util.List; импорт java.util.ArrayList; общественного класса комбинаторика {государственной статической силы основных (String [] агдз) {список List = новый ArrayList (); INT [] обр = {1,2,3,4,5}; combinations3 (обр, список); listToString (список); } Статической силы combinations3 (INT [] обр, список Список) {для (INT I = 0; я
Esostack
23

голосов
6

ответ
577

Просмотры

Picking unordered combinations from pools with overlap

У меня есть бассейны ценностей, и я хотел бы, чтобы генерировать все возможные комбинации неупорядоченных, выбирая из некоторых бассейнов. Например, я хотел бы забрать из бассейна 0, бассейн 0 и бассейн 1: >>> бассейны = [[1, 2, 3], [2, 3, 4], [3, 4, 5]] >> > часть = (0, 0, 1) список >>> (продукт (* (пулы [I] для I в части))) [(1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 3), (1, 3, 4), (2, 1, 2), (2, 1, 3), (2, 1, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4) , (2, 3, 2), (2, 3, 3), (2, 3, 4), (3, 1, 2), (3, 1, 3), (3, 1, 4), ( 3, 2, 2), (3, 2, 3), (3, 2, 4), (3, 3, 2), (3, 3, 3), (3, 3, 4)] Это создает каждый возможные комбинации, выбирая из бассейна 0, бассейн 0 и бассейна 1. Однако порядок не имеет значения для меня, так что многие из комбинаций фактически дублирует. Например, так как я использовал декартово произведение, как (1, 2, 4) и (2, 1, 4) генерируются. Я придумал простой способ, чтобы смягчить эту проблему. Для членов выбираются из одного пула, я выбираю без заказа с помощью combinations_with_replacement. Я сосчитать, сколько раз я хочу сделать из каждого пула. Код выглядит следующим образом: CNT = Счетчик () для отра в части: CNT [Ind] + = 1 блоков = [combinations_with_replacement (пулы [я], CNT [я]) для я в CNT] возвращение [список (цепь (* комбо)) для комбо в продукте (* блоки)] Это уменьшает приказывая дубликаты, если я случайно выбрать один из нескольких раз же бассейн. Однако все бассейны имеют много перекрытия, и использование combinations_with_replacement на нескольких пулов слит будет генерировать некоторые недопустимые комбинации. Есть ли более эффективный метод для создания маркированных комбинации? Изменить: дополнительная информация о входах: Число частей и бассейнов мало (~ 5 и ~ 20), и для простоты, каждый элемент представляет собой целое число. Реальная проблема, я уже решил, так что это только для академического интереса. Скажем, есть тысячи сотни целых чисел каждого пула, но некоторые бассейны маленькие и только десятки. Так что какое-то союз или перекрестка, кажется, путь.
qwr
23

голосов
1

ответ
20.8k

Просмотры

PHP: Как получить все возможные комбинации 1D массив? [Дубликат]

Можно создать дубликат: алгоритм, который будет принимать номера или слова и найти все возможные комбинации комбинации, диспозиции и Перестановки в PHP Я прочитал / пробовал много предложенных ответов на SO, что ни один из них не решает проблему массива $ = массив ( 'Альфа », 'бета', 'Гамма'); Как получить все возможные комбинации? Ожидаемый результат: массив ( «Альфа», «бета», «Гамма», «Альфа-Бета», «Альфа-Гамма», «Бета Альфа», «Бета Гамма», «Гамма-Альфа», «Гамма Бета», «Альфа-Бета Гамма ', „Альфа Гамма Бета“, „Бета Альфа Гамма“, „Бета Гамма Альфа“, „Гамма Альфа Бета“, „Гамма Бета Альфа“) Примечание: ответ я ищу должен включать в себя все комбинации и все различные механизмы. Например: «Альфа Бета» и «Бета Альфа» 2 разные строки и оба должны быть в выходном массиве. заранее спасибо
evilReiko
22

голосов
1

ответ
24.4k

Просмотры

Получите уникальные комбинации элементов из списка питона [дублировать]

Этот вопрос уже есть ответ здесь: Как получить все возможные комбинации элементов списка в? 23 ответов Edit: Это не точная копия Как получить все возможные комбинации элементов списка в? Эта тема о поиске уникальных комбинаций, а другая тема о поиске всех комбинаций. Если у меня есть список Python: L = [1,2,3,4], что это лучший способ, чтобы получить все возможные уникальные комбинации из 3 элементов из списка, как показано ниже: [ «1,2,3», «1, 2,4" , „2,3,4“, „3,4,1“] порядок элементов в комбинациях не имеет значения. Например, «1,2,3» и «3,2,1» будет считаться одной и той же комбинации. Я, вероятно, может написать несколько петель, чтобы сделать это, но я думаю, что там может быть один вкладыш, который может сделать то же самое.
Allen
22

голосов
4

ответ
23.4k

Просмотры

Генерировать все комбинации-плюс массива с длиной в пределах заданного диапазона

Как я могу генерировать все возможные комбинации элементов массива с длиной в пределах заданного диапазона? Например:. ( 'А' .. 'е') to_a.all_possibilities (3, 5) следует производить массив, как: [ 'ABC', 'абд', 'Abe', 'ABF', ..., «ABCDE », 'ABCDF', 'abcda', ...] в том числе от "ABC"(три символа) до последней возможной комбинации ( 'а' .. 'F'). to_a с длиной пять символов. Я понятия не имею, как это сделать. Любая помощь?
fschuindt
22

голосов
15

ответ
48.1k

Просмотры

Как подсчитать возможные комбинации для монет проблемы

Я пытаюсь реализовать задачу монеты, спецификация Проблемы, как это создать функцию, чтобы посчитать все возможные комбинации монет, которые могут быть использованы для данной суммы. Все возможные комбинации для данного количества = 15 типов монет = 1 6 7 1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 2) 1 , 1,1,1,1,1,1,1,1,6, 3) 1,1,1,1,1,1,1,1,7, 4) 1,1,1,6,6 , 5) 1,1,6,7, 6) 1,7,7, прототип функции: INT findCombinationsCount (целое количество, Int монет []) Предположим, что массив монет сортируется. для вышеприведенного примера эта функция должна возвращать 6. Любой наставит меня, как осуществить это ??
Preetam Purbia

Связанные вопросы