Подскажите алгоритм: выбрать макс. непохожие варианты из множества
Так тебе критерий непохожести тоже придумать нужно?
Посмотри в сторону геометрии. Позиционируй упорядоченный набор чисел N как вектор. Тогда у тебя возникнет множество параметров, по которым их можно сравнивать. Да и объяснить другому свою модель задачи будет проще.
UPD: Значение в ячейке - это число?
Посмотри в сторону геометрии. Позиционируй упорядоченный набор чисел N как вектор. Тогда у тебя возникнет множество параметров, по которым их можно сравнивать. Да и объяснить другому свою модель задачи будет проще.
UPD: Значение в ячейке - это число?
ничего не понял. ты сравниваешь значения из разных диапазонов?
сформулируй в терминах векторов и множеств, а то на бред похоже.
сформулируй в терминах векторов и множеств, а то на бред похоже.
Для каждой ячейки набор свой и с другими наборами в общем случае сравниваться не может.
Визуально
пусть {} определяет ячейку. Пусть их 2 штуки.
{A|B} {C|D|E}
То есть для первой ячейки диапазон из двух значений A и B, для второй из трех C, D и E. Значения из разных диапазонов не сравнимы.
Хотелось бы получать наборы вида
Значение из первой ячейки - Значение из второй
Так, чтобы они были максимально различные по любому критерию (другого, чем сравнить количество одинаковых значений в каждой ячейки, я не вижу - т.е. AC и AD - совпадают по одному значению, а AC и BD ни по одному).
Визуально
пусть {} определяет ячейку. Пусть их 2 штуки.
{A|B} {C|D|E}
То есть для первой ячейки диапазон из двух значений A и B, для второй из трех C, D и E. Значения из разных диапазонов не сравнимы.
Хотелось бы получать наборы вида
Значение из первой ячейки - Значение из второй
Так, чтобы они были максимально различные по любому критерию (другого, чем сравнить количество одинаковых значений в каждой ячейки, я не вижу - т.е. AC и AD - совпадают по одному значению, а AC и BD ни по одному).
{A|B} {C|D|E}дык ответ для этой задачи какой?
такой?
{AC, BD}, {AC, BE}, {AD, BC}, {AC, BE}, {AE, BC}, {AE, BD}
и убери из условия слово максимльно
потому что совсем непонятно кто максимальнее C или D
Максимально различные условие необходимо, чтобы вариант AC и AD не подошел, если требуемое число результатов <= 6, иначе подобная пара должна быть включена в ответ чтобы набрать нужное количество значений.
еще вопрос
что означает эта бредовая фраза
что означает эта бредовая фраза
По идее, по N можно динамически вычислить K и от этого плясать.
Пардон, действительно бред написал.
Имелось в виду
Можно динамически вычислить K (сколько позиций в ячейках могут совпадать, чтобы два набора считать непохожими) в зависимости от требуемого количества результатов, так например:
Если для {A|B} {C|D|E} требовалось бы найти не более 6 результатов, то задав K = 0, получили бы максимально различные наборы (K = 1 не подходит, т.к. AC и AD могли бы попасть например если бы надо было найти больше 6, то надо K положить 1.
Имелось в виду
Можно динамически вычислить K (сколько позиций в ячейках могут совпадать, чтобы два набора считать непохожими) в зависимости от требуемого количества результатов, так например:
Если для {A|B} {C|D|E} требовалось бы найти не более 6 результатов, то задав K = 0, получили бы максимально различные наборы (K = 1 не подходит, т.к. AC и AD могли бы попасть например если бы надо было найти больше 6, то надо K положить 1.
хехе
и вправду комбинаторика
и вправду комбинаторика
Полностью различных(не совпадающих ни по одной ячейке) наборов будет столько, сколько различных значений в самом коротком диапазоне.
Да, это понятно.
Черт, опять натупил. Все никак не получается формализовать задачу
Черт, опять натупил. Все никак не получается формализовать задачу
Да и в общем, если есть k ячеек с диапазонами (0, 1 ... , (D_i) - 1) у i-ой ячейки то чтобы сделать j-ю последовательность надо взять значения:
{ j mod D_0, j mod D_1, ..., j mod D_(k-1) }
{ j mod D_0, j mod D_1, ..., j mod D_(k-1) }
Да и в общем, если есть k ячеек с диапазонами (0, 1 ... , (D_i) - 1) у i-ой ячейки то чтобы сделать j-ю последовательность надо взять значения:красиво
{ j mod D_0, j mod D_1, ..., j mod D_(k-1) }
токо никак не помогает изначальную задачку решить
А что мешает использовать это в начальной задаче? Просто пронумеровать значения в каждом диапазоне от 0 до конца. А если в диапазоне бесконечное число значений то в каждой следующей последовательности надо использовать любое, еще неиспользованное значение.
Все никак не получается формализовать задачухехе
попытался формализовать
и понял что я так и не понимаю что ты хочешь
давай конкретные примеры и конкретные ответы
пример 1
дано: {A}, {B}
ответ для K=1:
ответ для K=2:
ответ для K=3:
пример 2
дано: {A}, {BС}
ответ для K=1:
ответ для K=2:
ответ для K=3:
пример 3
дано: {AD}, {BС}
ответ для K=1:
ответ для K=2:
ответ для K=3:
А месье не хочет случаем просто ортогональные массивы (для подмножеств ячеек размера не больше некоторого t все комбинации значений в них встречаются равновероятно)? Есть уйма алгоритмов их построения - возможно удастся найти с подходящими параметрами.
Спасибо откликнувшимся. При попытке еще больше формализировать задачу, случайно нашел решение 
Пусть имеется список всех возможных вариантов.
Сначала выбираем из него в другой список те наборы, которые никак не похожи (K = 0)
Потом из исходного списка выбираем те, которые похожи ровно в одной ячейке (K = 1 и добавляем их к имеющемуся списком с K = 0.
...
Продолжаем набирать из исходного списка наборы до тех пор, пока не наберем требуемое количество или пока величина полученного списка не сравняется с величиной исходного списка.
Пусть имеется список всех возможных вариантов.
Сначала выбираем из него в другой список те наборы, которые никак не похожи (K = 0)
Потом из исходного списка выбираем те, которые похожи ровно в одной ячейке (K = 1 и добавляем их к имеющемуся списком с K = 0.
...
Продолжаем набирать из исходного списка наборы до тех пор, пока не наберем требуемое количество или пока величина полученного списка не сравняется с величиной исходного списка.
Имелось в виду вот это
Пример1
K = 1, 2: AB
Пример2
K=1: AB и AC
K = 2: AB или AC
Пример3
K = 1: AB, AC, DB, DC
K = 2: напр. пара AB и AC
3 - не имеет смысла, т.к. позиций выбора всего 2.
Пример1
K = 1, 2: AB
Пример2
K=1: AB и AC
K = 2: AB или AC
Пример3
K = 1: AB, AC, DB, DC
K = 2: напр. пара AB и AC
3 - не имеет смысла, т.к. позиций выбора всего 2.
Пример1сил моих нет
K = 1, 2: AB
Пример2
K=1: AB и AC
K = 2: AB или AC
Пример3
K = 1: AB, AC, DB, DC
K = 2: напр. пара AB и AC
ты фактически ничего не ответил
я тебя просил ЧЕТКО сказать что должно быть в ответе
слова "напр." и "или" означают что ответов несколько и на экран выведется какойнить - это понятно
но что означают следующие слова: "," "и", "пара" - СОВСЕМ НЕ ПОНЯТНО
что ты подразумеваешь под K?
я думал что K - это у тебя количество наборов которые будут в ответе, и это входное данное (так же как N)
но у тебя уже в первом примере при K=2 в ответе один набор а не два
если же ты под K подразумеваешь "чсло совпадений" наборов, то у тебя во втором примере при K=2 нету никаких двух совпадений
Да,
ИЛИ подразумевался любой из вариантов
И только такой набор.
НАПР, означает что итоговый набор может быть один из нескольких.
K - это число ячеек в которых есть совпадение.
Входной параметр, помимо набора ячеек с множеством их выбора {AB} {CDE}..., только один - количество результатов, ожидаемых на выходе, так чтобы они были наименее похожи.
Сорри за сбивчивые объяснения. На работе плохо думалось, а дома я уже кодю алгоритм вовсю
ИЛИ подразумевался любой из вариантов
И только такой набор.
НАПР, означает что итоговый набор может быть один из нескольких.
K - это число ячеек в которых есть совпадение.
Входной параметр, помимо набора ячеек с множеством их выбора {AB} {CDE}..., только один - количество результатов, ожидаемых на выходе, так чтобы они были наименее похожи.
Сорри за сбивчивые объяснения. На работе плохо думалось, а дома я уже кодю алгоритм вовсю
ты не ответил на вопрос
но у меня есть большое подозрение что ты не понимаешь что хочешь, а потому алгоритм который ты накодишь работать будет ну совсем непонятным образом
я вот пока даже не понял какие сущности должны быть в ответе: наборы или множества наборов
если наборы - то K вообще бессмысленно
если множества наборов, но непонятно сколько элементов-наборов может быть в этих множествах
A - элемент
AC - набор
{AC, AD} - множество наборов
K - это число ячеек в которых есть совпадение.
у тебя во втором примере при K=2 нету никаких двух совпаденийалгоритм то ты может и кодишь
но у меня есть большое подозрение что ты не понимаешь что хочешь, а потому алгоритм который ты накодишь работать будет ну совсем непонятным образом
я вот пока даже не понял какие сущности должны быть в ответе: наборы или множества наборов
если наборы - то K вообще бессмысленно
если множества наборов, но непонятно сколько элементов-наборов может быть в этих множествах
A - элемент
AC - набор
{AC, AD} - множество наборов
Да вроде все ок с алгоритмом.
Попробую еще раз:
Есть пронумерованные ячейки от 1 до N, обозначаемые {}.
Для каждой ячейки определен набор значений, которые в нее можно поместить. Обозначение ячейки и набора {ABC}
Если в КАЖДУЮ ячейку поместить ОДНО из возможных для ячейки значений, то получим некий набор значений (набор).
Необходимо получить множество наборов, такое что
1. Количество наборов в этом множетсве не превосходит задаваемого заранее числа
2. Наборы максимально отличались друг от друга по любому критерию (я выбрал критерий по которому два набора отличны, если имеют имеют не более K ячеек с одинаковыми значениями).
Два мне Совсем объясняться разучился.
Попробую еще раз:
Есть пронумерованные ячейки от 1 до N, обозначаемые {}.
Для каждой ячейки определен набор значений, которые в нее можно поместить. Обозначение ячейки и набора {ABC}
Если в КАЖДУЮ ячейку поместить ОДНО из возможных для ячейки значений, то получим некий набор значений (набор).
Необходимо получить множество наборов, такое что
1. Количество наборов в этом множетсве не превосходит задаваемого заранее числа
2. Наборы максимально отличались друг от друга по любому критерию (я выбрал критерий по которому два набора отличны, если имеют имеют не более K ячеек с одинаковыми значениями).
Два мне
Совсем объясняться разучился.Необходимо получить множество наборов, такое чторешение это задачи очевидно: всегда выдавать в ответ множество наборов состоящее из одного набора
1. Количество наборов в этом множетсве не превосходит задаваемого заранее числа
2. Наборы максимально отличались друг от друга по любому критерию (я выбрал критерий по которому два набора отличны, если имеют имеют не более K ячеек с одинаковыми значениями).
1. один набор не превосходит задаваемого заранее числа - выполнено
2. для одного набора очевидно выполнено
т.е. например для задачи {ABCDEFG}, {123456}, {абв} для любого задаваемого заранее числа в ответ выдавать: {A1а}
так что ты опять хреновое условие задачи поставил
у меня уже спортивный интерес
хочется таки понять что ты хочешь
хочется таки понять что ты хочешь
Упс, точно.
Надо множество наборов. При этом в нем должно быть N элементов (если возможно, т.е. повторения наборов не допускаются).
Тупняк у меня какой то.
Надо множество наборов. При этом в нем должно быть N элементов (если возможно, т.е. повторения наборов не допускаются).
Тупняк у меня какой то.
Я думаю, он просто ошибся в примере два три (там должно быть AC и BD)
Ну и вообще хватит уже с душевнобольными общаться. Видно же, что у пациента поток сознания неконтролируеммый, а ты там какую-то логику ищешь.
Ну и вообще хватит уже с душевнобольными общаться. Видно же, что у пациента поток сознания неконтролируеммый, а ты там какую-то логику ищешь.
он просто ошибся в примере два (там должно быть AC и BD)ну нету в примере два буквы D
Надо множество наборов. При этом в нем должно быть N элементов (если возможно, т.е. повторения наборов не допускаются).опять как попало пишешь
видимо имеется ввиду
Надо множества наборов. При этом в каждом из них должно быть N наборов (если возможно, т.е. повторения наборов не допускаются).это чуть ли не первая осмысленная фраза, особенно ее последняя часть
еще бы понять что значит "если возможно", имеется наверна ввиду что в ответе должны быть все варианты
смотрим пример3: {AB}, {CDE}
тот алгоритм который ты ща реализуешь делает следующее:
вытаскиваем все множества наборов для которых максимальное попарное число K равно нулю
это: {AC}, {AD}, {AE}, {BC}, {BD}, {BE}, {AC BD}, {AC BE}, {AD BC}, {AD BE}, {AE BC}, {AE BD}
потом вытаскиваем все множества наборов для которых максимальное попарное число K равно единице
{AC AD} {AC AE} {AD AE} {BC BD} {BC BE} {BD BE}
и еще {AC BC} {AD BD} {AE BE}
а также {AC AD BE} {AC AE BD} {AD AE BC} {BC BD AE} {BC BE AD} {BD BE AC}
а также {AC AD BE BD} и так далее, там еще дохуя вариантов
для K=2 там тож дофига вариантов
ты конечно скажешь что то что после "а также" не подходит т.к. N=2 и в наших множествах должно быть не больше двух элементов
тогда смотрим такой пример: {AB}, {CDE}, {KLM}
для K=1 будет и вот такое: {ACK ADL} ...
и вот такое {ACK ADL AEM} ...
и вот такое {ACK ADL BCL} ...
а вот эти типа не попадут: {ACK ADL BCL AEM BEK BDM} ...
пример 1и если в третьем примере попросили вывести 10 результатов, то выдавать один из 6 вариантов
дано: {A}, {B}
при K=0: {AB}
при K=1: -
при K=2: -
при K=3: -
пример 2
дано: {A}, {BС}
при K=0: {AB}, {AC}
при K=1: {AB AC}
при K=2: -
при K=3: -
пример 3
дано: {AD}, {BС}
при K=0: {AB}, {AC}, {DB}, {DC}, {AB DC}, {AC DB}
при K=1: {AB AC}, {DB DC}, {AB DB}, {AC DC}
при K=2: -
при K=3: -
это если "а также" проигнорировать
Достаточно ОДНОГО множества наборов (понятно, что оно неоднозначно определено и зависит от алгоритма) с числом элементов (каждый элемент - это "набор") в нем равным N (или меньше, если невозможно набрать неповторяющимися наборами N)
У нас с тобой разные обозначения:
мое {ABC} значит, что в ячейке может лежать либо A, либо B, либо C. AB в ячейке лежать, например, не может.
Т.е. если рассмотреть две ячейки с их множествами значений {ABC} и {DE}, то всевозможные наборы будут
AD (в первой ячейке A, во второй D)
AE
BD
BE
CD
CE
При этом наборы AE и CD имеют K = 0, а AE и CE имеют K = 1.
Вообщем зря я наверно для ячеек обозначение {} выбрал - у мехмата видимо стойкая ассоциация скобок ко множеству.
У нас с тобой разные обозначения:
мое {ABC} значит, что в ячейке может лежать либо A, либо B, либо C. AB в ячейке лежать, например, не может.
Т.е. если рассмотреть две ячейки с их множествами значений {ABC} и {DE}, то всевозможные наборы будут
AD (в первой ячейке A, во второй D)
AE
BD
BE
CD
CE
При этом наборы AE и CD имеют K = 0, а AE и CE имеют K = 1.
Вообщем зря я наверно для ячеек обозначение {} выбрал - у мехмата видимо стойкая ассоциация скобок ко множеству.
вот тут очень сильно заблуждаешься
твои ячейки - это классическое множество, ты его совершенно правильно обозначил скобками
множество наборов - это тоже классическое множество, я его совершенно правильно обозначил скобками
а вот наборы формально надо обозначать круглыми скобками, ибо это последовательноть
ответ должен формально так обозначаться: {(ACK (BFG)}
а еще формальнее так: {(A,C,K (B,F,G)}
я в своих ответах опустил круглые скобки и запятые на пробелы заменил - для читаемости
т.е. в ответе {AC} - это {(A,C)}
в условии задачи {AC} - это ячейка
твои ячейки - это классическое множество, ты его совершенно правильно обозначил скобками
множество наборов - это тоже классическое множество, я его совершенно правильно обозначил скобками
а вот наборы формально надо обозначать круглыми скобками, ибо это последовательноть
ответ должен формально так обозначаться: {(ACK (BFG)}
а еще формальнее так: {(A,C,K (B,F,G)}
я в своих ответах опустил круглые скобки и запятые на пробелы заменил - для читаемости
т.е. в ответе {AC} - это {(A,C)}
в условии задачи {AC} - это ячейка
Оставить комментарий
0000
Имеется скажем N ячеек. В каждой ячейке может находится значение из определенного диапазона (для каждой ячейки диапазон свой).Надо выбрать максимально непохожие наборы, если имеется ограничение на их количество.
Пока что я сделал тупо:
Выставляется число K. Два набора будут считаться различными, если они имеют не более чем в K ячейках одинаковые значения.
Только вот с комбинаторикой у меня туго