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

1

голосов
1

ответ
99

Просмотры

Все перестановки в диапазоне с параметрами

Я пытаюсь найти эффективный алгоритм для решения следующей задачи. Дайте диапазон чисел от 1..N и некоторых произвольных чисел К и М, найти все возможные перестановки в заданном диапазоне. Где К представляет собой число элементов, и М представляет собой минимальное расстояние между элементами. Итак, давайте рассмотрим пример: массив = 1,2,3,4,5,6,7,8 К = 2 М = 2, так что выход тогда будет (3,5) (3,6) (4,6 ), так что вы можете увидеть, как увеличивается сложность, если K и M становится все больше. Приветствия.
hasskell
1

голосов
0

ответ
180

Просмотры

0-1 ранец: Найти множество решений в пространстве-оптимизированная реализация

Я хочу, чтобы решить 0-1 задачи о рюкзаке с максимальным весом ~ 200k и 100k над элементами и в конечном итоге определение элемента набора, а не только оптимального веса. Исследуя 0-1 ранце, я прочитал, что обычный способ решить эту проблему с помощью динамического программирования и создания таблицы, содержащей оптимальные решения подзадач, таким образом, раскалывается исходную задачу на более мелкие части, а затем обратной трассировки на столе, чтобы определить набор предметов , Максимальная прибыль, без учета элементов, взятых, может быть вычислен в памяти эффективным способом (как описано здесь). Очевидная проблема здесь в том, что для размерностей я имею в виде, этот подход будет потреблять больше памяти, чем это возможно (требуется O (N * W) пространство с п-числом элементов и W является максимальной мощностью). Исследуя далее я нашел упоминание (здесь, например, Также в раздел «Проблемы ранца» по Kellerer, Pferschy и Pisinger) запоминающего устройство эффективного способа решения 0-1 ранца. Мы начинаем раскалывается элемент установлен на два подмножества, примерно равные по размеру. Мы рассматриваем оба подмножества как свои собственные задачи о рюкзаке, учитывая первоначальный максимальный вес W и определить последнюю строку расчета максимальной прибыли для обоих подмножеств в памяти эффективным способом (подробно описано выше). Следующий шаг, чтобы выяснить, где оптимально разделить два подмножества. Для этого, мы определяем максимальную прибыль для веса w1 и w2 из двух строк. Как я понимаю, это имеет решающее значение для поддержания w1 + w2 = W, так что я итерация по первой строке и принимать индекс на противоположном конце текущего индекса. Моя текущая реализация этого шага выглядит следующим образом: раскол четкости (весы, значение, п, ш, г): # S1 является тем больше размера подмножества, если п не является даже s1 = N // 2 + (N & 1) с2 = п // 2 row1 = maximum_profit (вес, значение, s1, ш) row2 = maximum_profit (вес [s1:], значения [s1:], с2, ш) max_profits_for_capacity = [х + у для х, у в молнии (row1, row2 [:: - 1])] max_profits = макс (max_profits_for_capacity) optimal_weight_index = max_profits_for_capacity.index (MAX_VALUE) с1 = row1 [optimal_weight_index] c2 = row2 [ш-optimal_weight_index-1] c1 и c2 максимальную прибыль для каждого из подмножеств, то при сохранении С1 + с2 = W. С этими значениями мы RECURSE в каждом из подмножеств: расщепленные (вес [ : s1] значение [: s1], s1, c1, я) расщепленный (вес [s1:], значение [s1:], s2, c2, я + s1) здесь описания потеряют меня. В конце концов, этот код будет рекурсию к п == 1 со значением ш. Как определить, если элемент включен данный индекс элемента я и максимальный (локальный) емкость ж? Я могу предоставить небольшой пример набора данных для иллюстрации разработки моего кода в деталях и где идет не так. Большое спасибо.
Sven Jakub
1

голосов
1

ответ
129

Просмотры

Возвращайтесь подмножества в рекурсии - Python

Я должен реализовать рекурсивную функцию, которая recieves только два аргумента: «п» и «K», где п есть длина набора от «0» до «п-1» и & длина подмножеств отличаются элементы из исходного набора. Мы должны вернуться, наконец, список списков, содержащий эти все вложенные списки в к-длины. Поворот здесь, что я не знаю, чтобы преодолеть это, мы не должны использовать другие аргументы, такие как списки, кортежи, наборы и т.д. ... Так что я не знаю, как «сохранить» в рекурсии список всех подмножеств без «потерянная» деталь. Защиту ret_k_subset (N, K): если п> = 0 и к> = 0: LST = [], если Len (ЛСТ) == к: вернуть LST остальное: для п в диапазоне (N): обратный LST + ret_k_subset (п , к) возвращение LST Я думал, что-то подобное, но он всегда возвращает пустой список ... Так что я думаю, что нужно понять, как я могу сохранить структуры данных последовательно в рекурсии. Благодарю.
HelpMe
1

голосов
2

ответ
43

Просмотры

R: Найти все комбинации без замены разреженной матрицы

Я хочу, чтобы найти все возможные комбинации (без замены) большой разреженной матрицы. Каждая комбинация может выбрать максимум один раз из каждой строки и столбца. Моя цель состоит в том, чтобы найти комбинацию, которая максимизирует сумму выбранных записей. Скажем, у меня есть следующая матрица: 6 8. , , 5 7. , 6. 9 Существуют 4 возможные комбинации (в терминах I и J): [(1,1), (2,2), (3,4)], [(1,1), (2,3), (3 , 2)], [(1,2), (2,3), (3,2)], [(1,2), (2,3), (3,4)] Мой результат должен быть суммой записей для каждой возможной комбинации, где моя конечная цель состоит в том, чтобы найти комбинацию, которая максимизирует этот результат ([(1,2), (2,3), (3,4)] = 8 + 7 + 9 = 24 в этом пример). Изменить: вот полный код, который генерирует разреженную матрицу из которых я хочу найти оптимальное сочетание: библиотека (data.table) библиотека (ggplot2) библиотека (приют) библиотека (Matrix) библиотека (EVD) set.seed (12345) N1
Muly
1

голосов
2

ответ
483

Просмотры

Specific combination algorithm

Если у меня есть п шаров и к емкости, то это -> (!! (П + к-1) / п (к-1)) будет работать, сколько комбинаций есть. У меня возникают трудности при изменении этого, чтобы получить список всех комбинаций в JavaScript. В функции принимает массив шаров и некоторое количество контейнеров. Комбинации ([1,2,3,4,5,6], 3) Каждый контейнер может иметь любое количество шаров и контейнеры могут быть пустыми. Вот что-то я пытался, но им только получать один мяч в каждом контейнере. Функция generateCombinations (массив, г, обратный вызов) {функция, равная (а, б) {для (вар я = 0; г <a.length; я ++) {если (а [I] = Ь [I]!) возвращают ложь; } Возвращает истину; } Значения функции (я, а) {вар RET = []; для (вар J = 0; J <i.length; j ++) ret.push (а [я [J]]); вернуться в отставке; } Вар п = array.length; Индексы вар = []; для (вар я = 0; я <г; я ++) indices.push (I); Окончательный вар = []; для (вар я = п - г; <п; я ++) final.push (I); в то время как (равные (индексы, окончательный)) {обратного вызова (значения (индексы, массив)); вар я = г - 1; в то время как (индексы [I] == п - г + I) I - = 1; Индексы [I] + = 1; для (вар J = I + 1, J <г; J ++) Индексы [J] = индексы [I] + J - я; } Обратного вызова (значение (индексы, массив)); } Count = 0 generateCombinations ([1,2,3,4,5,6,7,8,9,1], 3, функция (первая) {$ ( "# привет"). Добавить (первый + "") подсчет = кол +1}) $ ( "# Hello"). добавить (количество) в то время как (индексы [I] == п - г + I) I - = 1; Индексы [I] + = 1; для (вар J = I + 1, J <г; J ++) Индексы [J] = индексы [I] + J - я; } Обратного вызова (значение (индексы, массив)); } Count = 0 generateCombinations ([1,2,3,4,5,6,7,8,9,1], 3, функция (первая) {$ ( "# привет"). Добавить (первый + "") подсчет = кол +1}) $ ( "# Hello"). добавить (количество) в то время как (индексы [I] == п - г + I) I - = 1; Индексы [I] + = 1; для (вар J = I + 1, J <г; J ++) Индексы [J] = индексы [I] + J - я; } Обратного вызова (значение (индексы, массив)); } Count = 0 generateCombinations ([1,2,3,4,5,6,7,8,9,1], 3, функция (первая) {$ ( "# привет"). Добавить (первый + "") подсчет = кол +1}) $ ( "# Hello"). добавить (количество)
Matt Saddington
1

голосов
2

ответ
69

Просмотры

Произвольный доступ к перечислению отсортированных наборов 3 символов из фиксированного алфавита

Представьте, что мы имеем алфавит, скажем, 5 символов: ABCDE. Теперь мы хотим, чтобы перечислить все возможные наборы 3 из этих букв. Каждая буква может присутствовать только один раз набор и порядок букв не имеет значения (отсюда буквы в наборе должны быть отсортированы). Таким образом, мы получаем следующие наборы: ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE В общей сложности 10 комплектов. Порядок лексикографический. Предположим теперь, что длина алфавита N (5 в этом примере) и длина набора в М (3 в этом примере). Зная N и M, как мы могли бы, если вообще возможно: Скажите общее число комбинаций в худшем O (M + N) (ответ 10 в данном примере)? Выход комбинации с любым заданным числом (1, заданного возврата ABC; дано 5, возвращение АПФ и так далее) в в худшем случае O (M + N)? Это тривиально, чтобы сделать эти вещи с O (^ N M) сложности, генерируя весь список,
dragonroot
1

голосов
4

ответ
85

Просмотры

Найти все альтернативные конкатенации 2 строки

Так что я пытаюсь написать функцию для нахождения всех альтернативных конкатенации 2 строки. Скажем, х = '12' и у = 'аb', то ожидаемый результат [ 'AB12', 'A1B2', 'a12b', '1ab2', '1A2B', '12ab']. Я написал следующую программу: # [список последовательностей, где каждый след является CONCAT s- и т] Защита г (s, т): # если (s == «»): возвращение [т] Элиф (т == ""): возвращение [с] еще: разреш = [] для я в xrange (LEN (ов)): для J в xrange (1, длина (т) + 1): res.extend ([s [: я] + T [: J] + х при х в г (ы [I:], т [J:])]) # res.append (s + T) возвращение рес Он выдает правильный результат, но некоторые последовательности имеют дубликаты: В работе [22]: г = г ( "12", "б" ) [(Х, r.count (х)) для х в наборе (R)] Выход [22]: [( 'AB12', 2), ( '12ab', 1), ( '1ab2', 2), ( 'a12b', 1), ( '1A2B', 1), ( 'A1B2', 1)] Как избежать дубликатов? (Я не хочу, чтобы проверить, является ли уже добавлен элемент, я заинтересован в «подлинном» способ создания уникальных последовательностей)
usual me
1

голосов
1

ответ
235

Просмотры

Найти все заказанные комбинации отфильтрованных элементов с помощью Linq

Я хочу, чтобы найти все заказанные комбинации строк отфильтрованных включать только те, с определенной строкой настоящего, учитывая следующую структуру: // элементы строки [] а = { «a1»}; Строка [] = {Ь "b1", "b2", "b3"}; Строка [] с = { "c1", "c2"}; // элемент группы строка [] [] т = {а, Ь}; Строка [] [] п = {а, Ь, с}; Строка [] [] о = {Ь}; Строка [] [] р = {Ь, с}; // элемент группы группировок строк [] [] [] groupGroupings = {M, N, O, P}; Учитывая groupGroupings и фильтруют, чтобы включать только комбинации, где, скажем, «b2» присутствует, то результат должен быть следующим: [ «a1», «b2»] [ «a1», «b2», «c1»] [» a1" , "b2", "c2"] [ "b2"] [ "b2", "c1"] [ "b2", "c2" ] У меня есть рекурсивный подход, который работает, но это немного некрасиво, и я не могу избавиться от ощущения, что есть более элегантный подход к этому. Я заинтересован в том, как что-то подобное может быть сделано, используя только LINQ, не уверен, если это возможно, но я не вижу его еще. Мой текущий подход: Список всех = новый список (); Foreach (VAR группы в groupGroupings) {вар комбо = FindAllCombinations (группы) .где (я => i.Any (г => g.Contains ( "b2"))) ToList (). all.Add (комбо); } Частного статические IEnumerable FindAllCombinations (строка [] [] группа) {если (groups.Length> 0) {вар группа = groups.First (); вар remainingGroups = groups.SkipWhile (! г => g.Equals (группа)) Пропустить (1). вар remainingCombinations = FindAllCombinations (remainingGroups.ToArray ()) ToList (). Еогеасп (вар элемент в группе) {если (remainingGroups.Count ()> 0) {Еогеасп (вар с в remainingCombinations) {Список комбо = новый список () {элемент}; combo.AddRange (с); выход возврата комбо; }} Еще выход вернуть новый список () {элемент}; }}}
genus
1

голосов
1

ответ
411

Просмотры

Проверьте Комбинаторные КНФ SAT Encodings?

Я пытаюсь решить комбинаторной задачи с помощью SAT Solver. Это включает в себя следующие шаги: закодировать проблему как набор логических выражений. Перевести конъюнкции выражений в УТС / DIMACS (с использованием домашнего выращены инструменты, bc2cnf, bool2cnf или Limboole) Решить CNF (с использованием SAT решатели, как Cryptominisat, Plingeling, Застежка или Z3) Перевести решение (при условии, результат на «SAT») назад в проблемной области Это работает в моем случае для малых выборок. Но для более сложных из них, решатель СБ занимает несколько часов или даже дней, не приходя к выводу, СБ / UNSAT. Я попробовать настроить мое кодирование, чтобы прийти к решению. Но чем больше усилий я ставлю в моей кодировке, тем меньше уверены, что я могу быть, что моя кодировка на самом деле правильно (т.е. «выполнимость эквивалента»). Шаг от логического выражения для КНФА является довольно запутанным, чтобы быть эффективными с точкой зрения числа управляемых статей и переменными. Больно ждать возраст для решателя SAT и не быть уверены, что время тратится на правильном пути. Логическое выражение может быть неправильным. Поэтому я хотел бы подтвердить, что УТС фактически представляет собой исходную задачу не просто логическое выражение. Мой вопрос: Как я могу проверить, что данное кодирование является действительным представлением исходного логического выражения? Из литературы, я знаю решения некоторых проблем, которые я мог бы перевести в значение переменной, чтобы получить доверие в моем процессе кодирования. Но из-за кодирование Цейтина, большинство переменных в моем УТСЕ является вспомогательным (переключение) переменное. Без кодирования Цейтина, мой CNF будет слишком большим, чтобы быть разрешимы. Поэтому я не могу просто проверить, если каждое предложение CNF выполнено известным решением. Я попытался перевести CNF обратно в логические выражения с использованием cnf2aig, но инструмент все еще находится в зачаточном состоянии. Без переключения переменных, то просто проверить в распайка против логических выражений первичной переменной задачи. Есть несколько публикаций о «УТС в цепи» подходов, но ни один из них не обеспечивает полезный инструмент. Есть ли лучшая практика для выполнения такой проверки? Есть несколько публикаций о «УТС в цепи» подходов, но ни один из них не обеспечивает полезный инструмент. Есть ли лучшая практика для выполнения такой проверки? Есть несколько публикаций о «УТС в цепи» подходов, но ни один из них не обеспечивает полезный инструмент. Есть ли лучшая практика для выполнения такой проверки?
Axel Kemper
1

голосов
1

ответ
1.8k

Просмотры

Как рассчитать большой комбинаторной функции в Matlab? [закрыто]

Я хотел бы найти следующую простую комбинаторную формулу в Matlab (nchoosek (п, к) * nchoosek (J, K) * nchoose (щ, ик)) / (nchoose (п, я) * nchoose (п, к)) но так как мои параметры являются большими Matlab возврата Inf как результат. Кто-нибудь знает о функции или инструмент, который может рассчитать эту формулу для меня?
H.Z.
1

голосов
1

ответ
659

Просмотры

Ways to create unique single elimination brackets

Я ищу способ, чтобы создать все возможные уникальные стартовые позиции для более N-плеера (N является степенью 2) турнира кронштейна выбывания (нокаут). Допустим, у нас есть игроки «A», «B», «C» и «D» и хотите, чтобы выяснить все возможные исходные позиции. Турнир будет выглядеть Tike это: А против В, С против D. Тогда победитель (AB) против победителя (CD). (Я буду использовать обозначения (A, B, C, D) для установки выше) Те были бы просто все возможные перестановки 4-х элементов, есть 4! = 24 из них, и это легко генерировать их. Но они не были бы уникальными для турнира, так как (A, B, C, D), (B, A, C, D), (B, A, D, C), (C, D, A, B ), ... было бы все это приводит к тем же матчам играются. В этом случае множество уникальных установок является, по-моему: (А, В, С, D), (А, С, В, D), (А, D, С, В) Все другие комбинации будет «симметричным ». Теперь мои вопросы были бы для общего случая N = 2 ^ й игроков: сколько таких уникальных установок есть? это известная проблема, которую я мог бы посмотреть? Не нашли еще. есть ли способ, чтобы генерировать их всех? как бы этот метод смотреть в Python (вопросы, ранжированных по воспринимаемой полезности) Я stumpled на этой записи, но это на самом деле не справиться с этой проблемой я обсуждаю здесь.
Dani Gehtdichnixan
1

голосов
1

ответ
2.2k

Просмотры

устранение Subtour ограничений симметричного коммивояжера в IBM CPLEX

Существует пример кода для задачи коммивояжера в IBM CPLEX. Он определил устранение subtour ограничение, как это: ForAll (ы в subtours) сумма (я в городах: s.subtour [I] = 0) х []
Nader
1

голосов
1

ответ
198

Просмотры

Быстрый комбинаторный генератор в Python

В рамках крупного проекта в Python, мне нужно быстро функцию генератора, который производит все возможные наборы неотрицательных целых чисел, меньших N, таким образом, что каждый набор имеет не более s элементов, а разница между наибольшим и наименьшим числом в множество меньше, чем вес. Самая быстрая реализация, что я достиг до сих пор использует itertools: въездной itertools DEF подвыборки (п, s, w): пп = диапазон (ш) для р в диапазоне (ы): O = (список itertools.combinations (пп, р + 1)) при т в о: выход т для _ в интервале (0, NW): Pt = оо = [кортежа ([оп + 1 для оп в списке (и)]) для и в п] для т в лист ((множество (о) ^ множество (PT)) и установить (о)): выход т например: В работе [1]: список (подвыборки (6,3,3)) Из [1]: [(0, ), (1), (2), (3), (4), (5), (0, 1), (0, 2), (1, 2), (1, 3) , (2, 3), (3, 4), (2, 4), (4, 5), (3, 5), (0, 1, 2), (1, 2, 3), (2, 3 , 4), (3, 4, 5)] Но я убежден, что должен быть более эффективные способы, чтобы сделать это. Есть ли что-нибудь, что бы сделать это быстрее?
STU
1

голосов
1

ответ
587

Просмотры

Печать лексикографически упорядоченные подмножества из заданной строки

Для экс - Если строка «ABC», то ответ должен быть абы а ас б Ьс с (всего лексикографический наималейшей комбинацией из набора символов должны появиться) я решить эту проблему, но для строки, содержащей 15 или более символов, оно занимает много времени. Как я могу уменьшить время работы моего алгоритма? Здесь п длина строки. Вот мой код: Int N = int.Parse (Console.ReadLine ()); вар ул = Console.ReadLine (); Строка Coll = string.Empty; Coll = Coll + "" + ул [0]; для (Int J = 1, J <N; j ++) {вар пунктов = coll.Split (»«); Еогеасп (вар элемент в пунктах) {Coll = Coll + "" + пункт + ул [J]; }} Вар тт = coll.Split (» ' ) .OrderBy (а => а); Еогеасп (вар пункт в ЦГ), если Console.WriteLine (пункт) (string.IsNullOrEmpty (пункт)!);
Naman
1

голосов
1

ответ
403

Просмотры

Рассчитайте число Bell в Matlab

Это то, что я уже реализованы: функция В = Колокол (п) В (1,1) = 1; для I = 2: п B (I, 1) = В (1, конец); при = 1: 1-я В (IJ, J + 1) = B (I-1, J) + В (I, J); конец конец конец При п = 3, я получил: 1 2 3 1 3 0 2 0 0 вместо: 1 2 3 5 1 0 2 0 0
1

голосов
1

ответ
204

Просмотры

Как реализовать дп?

Я недавно столкнулся с вопросом, где я дал два типа человека: левой рукой и правой рукой (стиль письма). Все они должны сидеть в классе строки и, чтобы избежать каких-либо нарушений их руки не должен конфликтовать, т.е. образец может быть как LR или LL или RR. Я попытался с помощью рекурсии (принимая две ветви L и R для каждого сиденья), но количество вычислений будет очень высокой, даже для размера строки из 100. Каким-то образом мне нужно реализовать DP, чтобы уменьшить вычисления. Просьба предложить. EDIT: На самом деле существует матрица (как класс), в котором три типа (ЛРБ) людей могут сидеть без каких-либо столкновений стороны. Я должен генерировать максимальное количество людей, которые могут быть установлены. Предположим, у меня есть матрица 2х2 и заполнить его влево, вправо и оба рукой типа лиц L = 0, R = 1, В = 3 приведены. Таким образом, один действительное расположение будет row0:
dark_energy
1

голосов
1

ответ
56

Просмотры

Efficiently generating “subtraction chains”

I posted another question earlier if you want some context. It appears that I was on the wrong path with that approach. Addition chains can be used to minimize the number of multiplications needed to exponentiate a number. For example, a7 requires four multiplications. Two to compute a2=a×a and a4=a2×a2, and another two to compute a7=a4×a2×a. Similarly, I'm trying to generate all of the possible "subtraction chains" for a set of numbers. For example, given the set of numbers {1, 2, 3}, I'm trying to generate the following permutations. {1, 2, 3} {1, 2, 3}, {1, 2} {1, 2, 3}, {1, 2}, {1} {1, 2, 3}, {1, 2}, {2} {1, 2, 3}, {1, 2}, {1}, {2} {1, 2, 3}, {1, 3} {1, 2, 3}, {1, 3}, {1} {1, 2, 3}, {1, 3}, {3} {1, 2, 3}, {1, 3}, {1}, {3} {1, 2, 3}, {2, 3} {1, 2, 3}, {2, 3}, {2} {1, 2, 3}, {2, 3}, {3} {1, 2, 3}, {2, 3}, {2}, {3} {1, 2, 3}, {1, 2}, {1, 3} {1, 2, 3}, {1, 2}, {1, 3}, {1} {1, 2, 3}, {1, 2}, {1, 3}, {2} {1, 2, 3}, {1, 2}, {1, 3}, {3} {1, 2, 3}, {1, 2}, {1, 3}, {1}, {2} {1, 2, 3}, {1, 2}, {1, 3}, {1}, {3} {1, 2, 3}, {1, 2}, {1, 3}, {2}, {3} {1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}, {3} # and so on... Where each element in the permutation (besides {1, 2, 3}) can be found by removing a single element from another set in the permutation. For example, the permutation {1, 2, 3}, {1} is invalid because {1} can not be constructed by removing a single element from {1, 2, 3}. Is there a known algorithm to find this subset of the power set of a power set? My implementation will be in Python, but the question is language agnostic. Also, I don't actually want the permutations which contain a set with a single element (e.g. {1, 2, 3}, {1, 2}, {1}) because they corresponds to a "dictator" case which is not of interest.
Jared Goguen
1

голосов
1

ответ
418

Просмотры

Java Сочетание поколения

Я ищу, чтобы увидеть, если Java имеет некоторые особенности, комбинаторика, что я могу использовать. Я хочу иметь динамический список, и в чистом виде, есть Java генерировать все комбинации. Учитывая список объектов, таких как строки ниже. Есть простой способ / чистый способ / предпочтительно что-то уже встроены в ядро ​​Java для создания всех комбинаций элементов? например, если у меня было: Список предметов = новый ArrayList (); items.Add ( "а"); items.Add ( "б"); Список результат = generateCombinationOf (элементы); Я желаю для результатов, чтобы содержать: {{}, { «а»}, { «б»}, { «а», «б»}} Примечание стороны: я был в состоянии генерировать списки, как это в Mathematica в прошлом. У меня есть проект стороны, где я хочу использовать Java, и я надеюсь, чтобы избежать интеграции с Mathematica, если это вообще возможно, но будет, если я могу»
James Oravec
1

голосов
2

ответ
77

Просмотры

Рассчитайте все способы бен ряд целых чисел в N бункера, где каждый бункер содержит только смежные номера

3], [4])])], [([0, 1, 2], [([3], [4])])]] Однако, как вы можете увидеть выход вложенными, так и для жизни меня, я не могу найти способ, чтобы правильно изменить код, не нарушая его. Желаемый результат будет выглядеть следующим образом: [20]: find_bins (начало = 0, остановка = 5, nbins = 3) Из [20]: [[(0), (1), (2, 3, 4)] , [(0), (1, 2), (3, 4)], [(0), (1, 2, 3), (4)], [(0, 1), (2), (3 , 4)], [(0, 1), (2, 3), (4)], [(0, 1, 2), (3), (4)]]
Paul Brodersen
1

голосов
1

ответ
72

Просмотры
1

голосов
1

ответ
177

Просмотры

Расчет размера полного внешнего соединения в панд

Т.Л., др Моя проблема в том, что я застрял в расчете, сколько строк предвосхитить на каждую часть полного внешнего слияния при использовании панд DataFrames как часть комбинаторики графа. Вопросы (повторялось ниже). Идеальное решение было бы не требовать слияний и запрос объектов панели. Учитывая, что это не метод запроса на панели есть чистое решение, которое позволит решить эту проблему, не задев потолок памяти? Если ответ на 2 нет, как я могу вычислить размер требуемой таблицы объединения для каждой комбинации наборов без проведения слияния? Это может быть неоптимальным подходом, но в данном случае это было бы приемлемо для целей применения. Является ли Python правильный язык для этого, или я должен смотреть на более статистическом языке, такие как R или записать его на более низком уровне (с, Cython) - Базы данных может быть и речи. Проблема Недавно я переписал фосфотирозинсодержащих расстроился графиков библиотеки, чтобы сделать его более эффективным с точки зрения времени при расчете комбинации по DataFrames. Я не ищу для рассмотрения этого кода, он прекрасно работает в большинстве случаев, и я доволен подходом. То, что я ищу в настоящее время является ответом на очень конкретную проблему; непокрытый при работе с большими наборами данных. Подход, который я взял с повторной записью был сформулировать слияние в памяти всех предусмотренных dataframes на полном внешнем соединение, как показан на линиях 480 - 502 из pyupset.resources для индекса ключа в Перечислять (ключи): каркасные = сам формат ._frames [ключ] frame.columns = [ '{0} _ {1}'. (колонка, ключ), если столбец не в себе. _unique_keys еще столбец для столбца в self._frames [ключ] .columns], если индекс == 0: self._merge = кадр еще:. суффиксов = ( '_ {0}' формат (клавиши [индекс-1]), «_ {0}». формат (клавиши [индекс]),) self._merge = self._merge.merge (рама, на = self._unique_keys, то как = 'внешние', копировальной = False, суффиксы = суффиксов) для малых и средних dataframes использования присоединяется работа невероятно хорошо. На самом деле последние тесты производительности показали, что он будет обрабатывать 5 или 6 наборов данных, содержащих 10000' х линий каждый в менее чем за минуту, которая является более чем достаточно для структуры приложения я требую. Проблема в настоящее время движется времени на основе памяти на основе из. Учитывая наборы данных потенциально 100s тысяч записей, библиотека очень быстро выбегает из памяти даже на большом сервере. Чтобы поместить это в перспективе, мой тест машина для этого приложения является 8-жильный VMWare коробка с 128GiB RAM работает Centos7. Учитывая следующие размеры наборов данных, при добавлении 5-dataframe, использование памяти спиралей в геометрической прогрессии. Это было довольно много ожидалось, но подчеркивает суть проблемы, я столкнулся. Ряды | Dataframe ------------------------ 13963 | dataframe_one 48346 | dataframe_two 52356 | dataframe_three 337292 | dataframe_four 49936 | dataframe_five 24542 | dataframe_six 258093 | dataframe_seven 16337 | dataframe_eight Это не "
mplf
1

голосов
1

ответ
35

Просмотры

Перечень шаров в корзине с определенным порядком

Я хотел бы перечислить решение с конкретным заказом. В настоящее время при коде ниже: Защиту balls_in_baskets (шарики = 1, корзины = 1): если корзины == 1: выход [шарики] ELIF шарики == 0: Выход [0] * корзины в другом месте, ибо я в диапазоне (шарики + 1): для J в balls_in_baskets (шарики-я, 1): для к в balls_in_baskets (я, корзины-1): выход J + кх = [т для т в balls_in_baskets (3,3)] [:: - 1] для я х: печать (I), я получаю это: [0, 0, 3] [0, 1, 2] [0, 2, 1] [0, 3, 0] [1, 0, 2] [1 , 1, 1] [1, 2, 0] [2, 0, 1] [2, 1, 0] [3, 0, 0] Тем не менее, хотелось бы этот порядок: [0, 0, 3] [0 , 1, 2] [1, 0, 2] [0, 2, 1] [1, 1, 1] [2, 0, 1] [0, 3, 0] [1, 2, 0] [2, 1, 0] [3, 0, 0] Как я могу добиться этого правильного порядка?
Isambard Mews
1

голосов
1

ответ
74

Просмотры

Выберите кластерные строки из таблицы

Я постараюсь написать свою проблему в списке, чтобы быть более понятным: У меня есть таблица MatLab T из размера 1000x30. Все данные в последней колонке под названием «Класс» в таблице имеет определенные значения целых чисел в диапазоне от 1 до 20. Таким образом, некоторые строки будут иметь значение 1, которое означает, что эти строки являются «Class1», а некоторые будут иметь значение 2 и некоторые из них будут иметь значение 20 и так далее. Количество строк, имеющих определенный класс не равно числу строк, имеющих другой класс, так что может быть есть 100 строк имеют класс 1, но 10 строки имеют класс 2 и 500 имеют класс 3 и так далее. Это то, что я хочу сделать: Я хочу, чтобы получить количество строк с классом, которые имеют наименьшее количество строк, возложенных на него. Так что давайте' скажем Класс 10 имеет наименьшее количество строк, возложенных на него с счета == 3, а остальные классы имеют более 3-х строк, возложенные на них. Я буду иметь новый столбец под названием YesNo, где он будет иметь только значение 0 или 1. Тогда все строк класса с наималейшим колом (например, класс 10 в этом примере) будет иметь значение 1. Для остальных строк с все другие классы, я хочу, чтобы случайным образом выбрать из любого другого класса примерно столько же строк, как класса с наименьшим номером (в данном примере это будет 3). Тогда для этих произвольно выбранных строк каждого другого класса значения в новом столбце YesNo будет 1, а для остальной части не выбранных строк будут равно 0. Таким образом, в этом примере, это будет в конечном итоге с новым столбцом с 1000 значений, где 3 * 20 из них будет иметь (3-> номер 1 по строкам, присвоенных классу с наименьшим числом, и 20-> это число классов) и 0 для остальных. Интересно, как это может быть сделано в MATLAB R2015b? Я знаю, что я могу создать новый столбец в таблице, используя T.YesNo = newArr; где newArr является 1000x1 вдвое, имеющими 0 и 1 значения. В качестве небольшого примера, если Т 10x3 и имеет только 3 классов (1,2,3), ниже, как выглядит Т: ID Имя класса 0 «а» 3 1 «B» 2 2 «» 2 3 «B» 2 4 'а' 3 '5' 1 6 '' 1 7 'B' 2 8 'B' 1 9 '' 2 Таким образом, как показано выше, Class3 является одним с наименьшим числом, где только две строки. Поэтому я хочу, чтобы случайно выбрать две строки каждого Class1 и Class2, а затем установите значения нового столбца этих произвольно выбранных строк 1, а остальное будет 0, как показано ниже: ID Имя класса YesNo 0 «а»
Tak
1

голосов
2

ответ
228

Просмотры

Равномерно выбор распределения элементов в бункера

Представьте, что у вас есть п элементов и т бункеров. Все детали идентичны, однако бункера различны. Какой самый быстрый алгоритм случайного выбора выделения элементов в закрома? Например - представьте себе 104 является размещение 5 элементов в 3-х бункеров. Есть 21 возможных размещения 5 предметов на 3 бункера: 005 014 023 032 041 050 104 113 122 131 140 203 212 221 230 302 311 320 401 410 500 Для получения большого количества элементов и контейнеров, как я должен выбрать расположение п элементов в м бункеров таким образом, что каждое возможное размещение имеет равные шансы происходит? Для данного п и м отбора будет сделано большое количество раз.
Jorge Perez
1

голосов
1

ответ
177

Просмотры

Combinations of items in array with multithreading using Swift

Я пишу небольшой алгоритм, и я должен рассчитать все возможные комбинации элементов в массиве без повторений. До сих пор я использовал этот код ниже, но теперь мне нужно, чтобы ускорить этот процесс, потому что это занимает слишком много времени. Я пытался реализовать параллелизм с Swift (код будет работать на Mac), но, к сожалению, она не работает. Алгоритм Я использую был взят из http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/, а затем преобразуется от с до Свифта. Не могли бы вы помочь мне решить эту проблему? FUNC printCombination (обр: [Int], г: Int) {trips.removeAll () вар данные: [Int] = [] для _ в 1 ... г {data.append (Int ())} combinationUtil (обр: обр, г: г, индекс: 0, данных: данные, я: 0)} функ combinationUtil (обр: [Int], г: Int, индекс: Int, данные: [Int], я:
Federico G
1

голосов
1

ответ
105

Просмотры

Как сделать копии массива в Python в зависимости от условий в массиве?

У меня есть п = np.array ([[1, 12, 1, 3], [1, 1, 12, 0]]) и хотели бы, чтобы дублировать ее таким образом, что если у меня есть двузначное число в массиве она разбивает массив на два идентичные массивы, где первый массив имеет первую цифру, а второй массив имеет вторую цифру. В приведенном выше примере, я бы 4 копии матрицы. Эти предположения, что либо одна цифра или двойные числа цифр в массиве. n1 = [1, 1, 1, 3], [1, 1, 1, 0] п2 = [1, 1, 1, 3], [1, 1, 2, 0] n3 = [1, 2, 1 , 3], [1, 1, 1, 0] n4 = [1, 2, 1, 3], [1, 1, 2, 0]
ZMP
1

голосов
1

ответ
71

Просмотры

Контроль комбинаторных аспектов динамического программирования решения

Я исследую, как динамический дизайн программирования подход относится к нижележащим комбинаторным свойствам задач. Для этого, я смотрю на каноническую экземпляр задачи обмена монет: Пусть S = [d_1, d_2, ..., d_m] и п> 0 будет запрашиваемая сумма. Сколько способов можно добавить до п, не используя ничего, кроме элементов в S? Если мы следуем динамического программирования для разработки алгоритма для этой задачи, которая позволила бы решение с полиномиальной сложностью, мы начнем с рассмотрения проблемы и как это связано с меньшими и более простых подзадач. Это дало бы рекурсивный соотношение, описывающее индуктивный шаг, представляющий проблему с точки зрения решения связанных с ней подзадач. Затем мы можем реализовать либо технику мемоизации или методику составления таблиц для эффективного осуществления этого рекурсивного соотношения в сверху вниз или снизу вверх таким образом, соответственно. Рекурсивное соотношение может быть следующий (Python 3.6 синтаксиса и 0 на основе индексирования): Защита C (S, M, N): если п <0: возвращать 0, если п == 0: возвращение 1, если т
Eduardo
1

голосов
2

ответ
438

Просмотры

Coin change with split into two sets

Я пытаюсь понять, как решить проблему, которая, кажется, хитрый вариант общей алгоритмической проблемы, но требует дополнительной логики для обработки конкретных требований. Учитывая список монет и сумму, мне нужно подсчитать общее число возможных способов извлечь данную сумму, используя неограниченное количество доступных монет (и это классическое изменение решений проблемы https://en.wikipedia.org/ вики / Переключение making_problem легко решается с помощью динамического программирования), которые также удовлетворять некоторые дополнительные требования: экстрагированные монеты расщепимы на две группы одинакового размера (но не обязательно равной сумма) порядок элементов внутри множества не имеет значения, но порядок в комплекте делает. Примеры Сумма 6 евро и монет [1, 2]: решения 4 [(1,1), (2,2)] [(1,1,1), (1,1,1)] [(2, 2), (1,1)] [(1,2), (1,2)] Количество 8 евро и монет [1, 2, 6]: решения 7 [(1,1,2), (1,1,2)] [(1,2,2), (1,1,1)] [(1,1,1, 1), (1,1,1,1)] [(2), (6)] [(1,1,1), (1,2,2)] [(2,2), (2,2 )] [(6), (2)] к настоящему времени я попробовал разные подходы, но единственный способ я нашел, чтобы собрать все возможное решение (с использованием динамического программирования), а затем фильтровать неразрываемый решение (с нечетным числом монет) и дубликаты. Я совершенно уверен, что есть комбинаторный способ вычислить общее количество дублирования, но я не могу понять, каким образом.
Andrea Mostosi
1

голосов
1

ответ
108

Просмотры

Есть функция для генерации конкретного п Multichoose комбинации г, учитывая порядковый номер?

Например, 3 multichoose 2 имеет следующие комбинации: я комбо 0 = [0,0] 1 = [0,1] 2 = [0,2] 3 = [1,1] = 4 [1,2] 5 = [2,2] Может ли функция быть записана, чьи аргументы п, г, я и возвращает комбинацию в вопросе, без перебора каждой комбинации перед ним?
yea
1

голосов
2

ответ
55

Просмотры

Ровно высокая карты в руке 6 карт с помощью моделирования

Так что у меня есть проблема, вероятность того, что (из чистой скуки), я решил попробовать и решить с помощью моделирования. Проблема: Какова вероятность рисования ровно одна старшей карты в руке 6 карт. Теперь эта проблема конкретно о какой-то игре, которая играла в моей стране, так по какой-то странной причине есть 21 высокие карты, но это не важно. Решение этой проблемы вручную, используя основные комбинаторика я получил: А теперь, вот, как я моделируется его в C: Основная функция: Int основной (вакуум) {srand (время (0)); INT палуба [52]; Int я; для (я = 0; я
Koy
1

голосов
2

ответ
0

Просмотры

Воссоздание входа для кодера с выхода

Я хотел бы понять, как решить эту проблему Codility ArrayRecovery, но я даже не знаю, что отрасль знания, чтобы проконсультироваться. Является ли это комбинаторика, оптимизация, информатика, теория множеств, или что-то еще? Edit: отрасль знаний для проведения консультаций является ограничением программирования, в частности, ограничение распространения. Кроме того, необходимо несколько комбинаторики, чтобы знать, что если взять к числам, в то время из диапазона [1..n], с тем ограничением, что ни один номер не может быть больше, чем до него, который работает, чтобы быть (п + к -1)! / к! (п-1)! возможные комбинации который является таким же, как количество комбинаций с заменами п вещей, принятых K в то время, которое имеет математические обозначения. Вы можете прочитать о том, почему это работает, как это здесь. Питер Норвиг является прекрасным примером того, как решать проблемы такого рода с его судоку решатель. Вы можете прочитать полное описание проблемы ArrayRecovery по ссылке выше. Коротко, то есть кодер, который принимает последовательность целых чисел в диапазоне от 1 до некоторого заданного предела (скажем, 100 для наших целей) и для каждого элемента входной последовательности выводит самое последнее время наблюдается целое число, которое меньше, чем входной ток, или 0, если ни один не существует. вход 1, 2, 3, 4 => выход 0, 1, 2, 3 вход 2, 4, 3 => выход 0, 2, 2 Полная задача, учитывая выход (и диапазон допустимых входных), рис , сколько возможно входы могли вызвать его. Но прежде, чем я даже получаю к этому расчету, я не уверен, о том, как даже приблизиться к формулировке уравнения. Это то, что я прошу помочь с. (Конечно, полное решение было бы только приветствовать, тоже, если это объясняется.) Я просто смотрю на некоторые возможные выходы и удивления. Вот некоторые примеры выходных сигналы энкодера и входы я могу придумать, с * означает любой действительный вход и что-то вроде> 4 значения любого действительного входа больше, чем 4. При необходимости, входы обозначаются как A1, A2, A3, .. . (1-индексирование) Редактировать # 2 Часть проблемы я имел с этой проблемой является то, что я не вручную генерировать точно правильные наборы возможных входов для выхода. Я считаю, что ниже набор является правильным в настоящее время. Посмотрите на истории изменений этого ответа, если вы хотите увидеть мои предыдущие ошибки. выход # 1: 0, 0, 0, 4 возможные входы: [> = 4, А1> = *> = 4, 4,> 4] выход # 2: 0, 0, 0, 2, 3, 4 # А5 ↴ подробнее в обсуждении ниже возможных входов: [> = 2, А1> = *> = 2, 2, 3, 4,> 4] выход # 3: 0, 0, 0, 4, 3, 1 возможные входы: нет # [4, 3, 1, 1> = *> 4, 4,> 1], но нет номера 1> = *> 4 Второй последовательность ввода очень жестко ограничена по сравнению с первым, просто добавив еще 2 выходов. Третья последовательность ограничена таким образом, чтобы невозможно. Но множество ограничений на A5 в примере № 2 немного сложнее сформулировать. Конечно A5> O5, что является основным сдерживающим фактором на всех входах. Но любой выход> A4 и после того, как O5 должен появиться на входе после A4, A5, так должно быть элементом множества чисел, которое приходит после того, как A5, который также> A4. Поскольку существует только один такой номер (А6 == 4), А5 должен быть, но это становится более сложным, если существует больше строки чисел, которые следуют. (Примечание редактора: на самом деле это не так.) Так как набор выходной становится больше, я переживаю эти ограничения просто получить сложнее и сложнее получить право. Я не могу думать о каких-либо структурах данных для эффективного представления их таким образом, что приводит к эффективному вычислению числа возможных комбинаций. Я тоже не совсем понимаю, как алгоритмический добавить ограничение устанавливает вместе. Вот ограничения я вижу до сих пор для любого заданного An An> On An On). Как определить набор возможных чисел больше, чем на? Числа больше, чем на том, что произошло после последнего появления On на входе An> = тах (множество других возможных чисел от O1 до п-1 <С). Как определить набор возможных чисел меньше, чем на? На самом деле это множество пусто, потому что на это, по определению, наибольшее возможное число от предыдущей входной последовательности. (Что не сказать, что это строго наибольшее число из предыдущей входной последовательности. ) Любое число меньше, чем на том, что было до последнего появления его на входе будет неподходящим из-за «ближайшие» правил. Нет число мелкого, что на могли произойти после последнего появления из-за «ближайшие» правил и из-за транзитивное свойство: если Ai <С и Aj <Ai, то Aj <О Тогда существует теория множеств: должен быть элемент множества неучтенных для элементов множества On + 1 Ом, где т наименьшее т> п такое, что Ом <Вкл. Любой выход после таких Ом и больше, чем Ом (что Ап) должен выступать в качестве или после Am. Элемент неучтенный, если он виден на выходе, но не появляется на входе в положении, которое согласуется с остальной частью производства. Очевидно, что мне нужно более точное определение, чем это для того, чтобы код и алгоритм его вычисления. Похоже, что, возможно, какой-то теории множеств и / или комбинаторики или, может быть линейной алгебры бы помочь выяснить количество возможных последовательностей, которые составляют для всех неучтенных выходов и соответствуют другим ограничениям. (Примечание редактора: на самом деле, вещи никогда не так уж сложно.)
Old Pro
1

голосов
2

ответ
0

Просмотры

Как получить п / 2-значные комбинации из п цифр

Я борюсь с этим алгоритмом. Он должен работать так: если я вход fé 6880, моя программа должна вывести 86 80 80 86 60 68 68. Как вы можете видеть, комбинации повторения. Это потому, что он смотрит на каждой цифре, так как это другой объект. В моей программе это правильно. Вот мой код: общественный статичный набор get2DCombinations (список цифры) {Set комбинация = новый TreeSet (); INT т = 0; для (Integer I: цифры) {для (целое число J: цифры) {т = I * 10 + J; если (т / 10> = 1) {combinations.add (т); }}} Возврата комбинаций; } Возвращает определенный набор комбинаций, в которых все комбинации имеют 2 цифры. Он отлично работает, но только с 4-х цифр. Конечно, я могу использовать еще один для каждого-петель, но есть способ автоматизировать? Поэтому, если я вход 6-значный номер он должен вывести все возможные 3-разрядные комбинации его цифр, а если вход 8-значный номер, он должен вывести все возможные комбинации 4-х цифр. Вводимые всегда есть даже количество цифр. Не могли бы вы указать, для меня, как это сделать?
nklymok
1

голосов
2

ответ
0

Просмотры

Алгоритм поиск возможного числа выборов

Я задал этот вопрос и дал это некоторое мысль, но не в состоянии решить. Возникает вопрос: Я попросил, чтобы выбрать п цветных карандашей. Есть карандаши K различной цветовой группы. Из каждой цветовой группы есть также бесконечно много карандашей. Я хочу, чтобы иметь по крайней мере один пучок каждой цветовой группы, но все еще есть много возможностей для моего выбора. Сколько возможностей для этого набора выбора можно иметь? Предположим, что пучок одинакового цвета не могут быть выделены, а также порядок карандашей не имеет значения.
Egalitarian
6

голосов
1

ответ
225

Просмотры

Генерация всех сочетаний списка п уровней глубоко в Java

Я использую следующий код, чтобы сгенерировать список комбинаций размера с: открытой статическим
Alan Cook
1

голосов
1

ответ
0

Просмотры

Алгоритм для расчета пара из класса п студентов для ш недель

Я ищу для алгоритма для вычисления пары из класса п (список имен студентов) для ш недель, так что студент никогда не взаимодействующий с таким же студентом, в двух разных неделях. Предположим, что п четно. Пример: класс: студенты 1,2,3,4 недели: 3 Расписание на неделю 1: (1,2), (3,4) график недели 2: (1,3), (2,4) график неделю 3: (2,3), (1,4) Я полагал, что вес должен быть меньше или равен п - 1, потому что каждый ученик может максимально сотрудничать с N - 1 других. Но я не знаю, если всегда есть п - 1 решений. Если есть, я хотел бы видеть АЛГОРИТМ, который генерирует этот п - 1 решение в доли не-переборе способе. Есть ли название для этой проблемы и общего алгоритма я должен смотреть?
Michiel Borkent
1

голосов
2

ответ
0

Просмотры

Организация задач на основе научных вычислений

У меня есть вычислительная алгебра задачи мне нужно написать код. Проблема разбивается на четко определенные индивидуум задачи, которые естественным образом образуют дерево - задача комбинаторная в природе, так что главная задача, которая требует небольшого количества вспомогательных расчетов для получения его результатов. Этот суб-расчеты имеют суб-суб-расчеты и так далее. Каждое вычисление зависит только от расчетов под ним в дереве (предполагается, что корневой узел является вершиной). Нет обмена данными не должно произойти между ветвями. При более низких уровнях количество подзадач может быть чрезвычайно большим. Я ранее закодирован это в функциональной моде, вызывая функции по мере необходимости и хранить все в памяти. Это был ужасный подход, но я был больше озабочен теорией тогда. Я планирую переписать код в C ++ по целому ряду причин. У меня есть несколько требований: Checkpointing: Расчет занимает много времени, так что мне нужно, чтобы быть в состоянии остановить в любой момент и возобновить позже. Отдельные индивидуальные задания в качестве объектов: Это помогает мне сохранить хорошую ручку, где я нахожусь в вычислениях, и предлагает чистый способ сделать с помощью контрольных точек сериализации. Многопоточность: Задача явно ошеломляюще параллельно, так что было бы опрятно, чтобы использовать это. Я бы, вероятно, хочу использовать Повысьте эффективность тему для этого. Я хотел бы предложения о том, как на самом деле внедрить такую ​​систему. Пути я думал сделать это: Реализация задач, как простой стек. Когда вы нажмете задачу, которая нуждается в subcalculations сделана, он проверяет, если у него есть все subcalculations требует. Если нет, то это создает подзадачи и бросает их в стек. Если это произойдет, то он вычисляет свой результат и хлопает себя из стека. Храните задачи в виде дерева и сделать что-то вроде глубины первого рисунка посетителя. Это создало бы все задачи на старте, а затем вычисление просто обход дерева. Они, кажется, не совсем правильно из-за проблемы на более низких уровнях, требующих огромное количество подзадач. Я мог бы подойти к нему в итератора моды на этом уровне, я думаю. Я чувствую, что я чрезмерно думая, что это и есть уже простой, устоявшийся способ сделать что-то вроде этого. Есть один? Технические детали в случае, если они имеют значение: Дерево задач имеет 5 уровней. Ветвление фактор дерева действительно мало (скажем, от 2 до 5) для всех уровней, за исключением самых низких, которая составляет порядка нескольких миллионов. Каждая отдельная задача нужно только хранить в результате десятков байт больших. Я не против использования диска, насколько это возможно, так долго, как это Безразлично» т убить производительность. Для отладки, я должен был бы быть в состоянии вспомнить / пересчитать любую индивидуальную задачу. Все расчеты дискретная математика: расчеты с целыми числами, полиномами и группами. Нет с плавающей точкой на всех.
BrettW
1

голосов
1

ответ
0

Просмотры

php array combinatorics/combination analyzes

Мне нужно, чтобы обнаружить все возможные комбинации для некоторых массивов, которые имеют конкретный символ. позволь мне объяснить. У меня есть этот текст, которые имеют векторы, организованные в виде строк: тысяча триста сорок две; - +, V +, -, V, V, V; НД; -; -; НД; НД; + +; НД; -; НД; ND ; ND; - +; НД; +; -; -; -; НД; -; -; НД; НД; -; НД; НД; F, Н. Д. 2343; -; -; -; -; -; -; НД; -; НД; -; -; НД; НД; -, V; НД; V; НД; НД; НД; - +; НД; -; -; -; В; НД; В; -; НД; НД; -; НД; НД; O, Н. Д. 2344; -; -; -; -; -; -; НД; -; НД; -; НД; НД; НД; НД; +; НД +; НД; Н.Д. ; НД; - +; НД; +; -; -; -; НД; V; НД; НД; НД; -; НД; НД; O, Н. Д. 2345; -, V, V +, V, V; НД; - +; -; -; -; НД; -, V; НД +; НД; V; НД; - +; НД; -; -; -; -; В; - +; НД; НД; -; -; +; Р; - каждая строка представляет собой vector..the значения атрибутов separeted с помощью ";" все возможные значения: числа, +, -, O, F, ND и «V», но символ V означает + и - то, что мне нужно, чтобы это проверить для каждой строки, когда вектор имеет в любом атрибут объявления полукокса «V " потому что если есть это означает, что эта строка должна быть воспроизведена на все возможности В.См. этот маленький пример: 109; +; -; В; ND; + Я проверил, что эта строка имеет один или более чем один «V», так что теперь просчитывает все возможности, которые могут быть сгенерированы для этой строки, как мы знаем, V = + и - так что эта одна строка будет генерировать: 109; +; -; +; ND; + 109; +; -; -; ND; + Как у нас есть только один V, поэтому мы будем иметь 2 возможности ... проблема в том, когда есть больше чем один «V» .. как рассчитать все возможные комбинации к нему .. при создании нового текста со всеми строками комбинаций нового текст не должен содержать происхождения строки с «V». обратите внимание, что все другие значения атрибутов остается неизменным. благодарю вас, + Я проверил, что эта строка имеет один или более чем один «V», так что теперь просчитывает все возможности, которые могут быть сгенерированы для этой строки, как мы знаем, V = + и - так что эта одна строка будет генерировать: 109; +; -; +; ND; + 109; +; -; -; ND; + Как у нас есть только один V, поэтому мы будем иметь 2 возможности ... проблема в том, когда есть больше чем один «V» .. как рассчитать все возможные комбинации к нему .. при создании нового текста со всеми строками комбинаций нового текст не должен содержать происхождения строки с «V». обратите внимание, что все другие значения атрибутов остается неизменным. благодарю вас, + Я проверил, что эта строка имеет один или более чем один «V», так что теперь просчитывает все возможности, которые могут быть сгенерированы для этой строки, как мы знаем, V = + и - так что эта одна строка будет генерировать: 109; +; -; +; ND; + 109; +; -; -; ND; + Как у нас есть только один V, поэтому мы будем иметь 2 возможности ... проблема в том, когда есть больше чем один «V» .. как рассчитать все возможные комбинации к нему .. при создании нового текста со всеми строками комбинаций нового текст не должен содержать происхождения строки с «V». обратите внимание, что все другие значения атрибутов остается неизменным. благодарю вас, проблема в том, когда есть больше, чем один «V» .. как вычислить все комбинации к нему .. при создании нового текста со всеми строками комбинаций нового текста не должен содержать происхождения строки с «V». обратите внимание, что все другие значения атрибутов остается неизменным. благодарю вас, проблема в том, когда есть больше, чем один «V» .. как вычислить все комбинации к нему .. при создании нового текста со всеми строками комбинаций нового текста не должен содержать происхождения строки с «V». обратите внимание, что все другие значения атрибутов остается неизменным. благодарю вас,
Omnia
1

голосов
3

ответ
0

Просмотры

линейной комбинаторной оптимизации

Пытаюсь выяснить алгоритмы лучше, чем грубая сила для решения этой комбинаторной оптимизации. Пример проблемы: Для достижения 2а + Ь при минимальной / максимальной стоимости комбинирования доступные линейных уравнений 1. 2а + Ь = 4 2. а = 1 3. а + Ь = 2 (РИТ является стоимость) Ответ: зерноуборочный 2 и 3, чтобы получить 2а + Ь = 3 метод грубой силы нахождения Powerset (все комбинации) компонента линейного уравнения, очевидно, не является оптимальным, когда целевое уравнение длительный и Powerset растет гигантскими. Является ли проблема вариант задачи о рюкзаке? Любые указатели о том, кто это может быть сделано оптимально?
gauravsaraf
1

голосов
2

ответ
653

Просмотры

Алгоритм, чтобы покрыть множество комбинаций к-М с подмножествами М

Я работаю над приложением, для которого я хочу взять множество С всех возможных к- комбинаций элементов в М (с || М || = т), и крышка C с наборами K-комбинации подмножеств n_i М, с || n_i || = п <т ∀ N_i Таким образом, существует (м) выбирают к комбинации, чтобы покрыть, и каждое множество q_i из п элементов будет содержать (п выбирают к) комбинации. То, что я хотел бы это алгоритм, который строит множества Qi такие, что д минимизируется (т.е., как можно ближе к (т выбрать к) / (п выбирают к), как это возможно) Так, например, если т = 100, к = 3, п = 10, я хотел бы наименьшее множество наборов элементов 10 таким образом, что их соответствующие наборы 3-х комбинаций покрыли набор (100 выбирают 3) 3-комбинации М.
Tom
1

голосов
3

ответ
531

Просмотры

Распределение MySQL комбинаций значений /

У меня есть таблица MySQL, который содержит случайную комбинацию чисел. Для простоты принять следующую таблицу в качестве примера: индекс | n1 | n2 | n3 1 1 2 3 2 4 10 32 3 3 10 4 4 35 1 2 5 27 1 3 и т.д. То, что я хочу, чтобы выяснить, является количество раз, сочетание произошло в таблице. Например, сколько раз имеет комбинацию 4 10 или 1 2 или 1 2 3 или 3 10 4 и т.д. произошло. Должен ли я создать еще одну таблицу, которая содержит все возможные комбинации и сделать сравнение оттуда или есть другой способ сделать это?

Просмотр дополнительных вопросов