Это вопрос о комбинаторике от не математика, поэтому, пожалуйста, старайтесь нести со мной!Алгоритм минимального изменения, который максимизирует «свопинг»
Учитывая массив из n различных символов, я хочу сгенерировать подмножества из k символов в порядке минимального изменения, то есть порядок, в котором поколение i + 1 содержит ровно один символ, который не был в генерации i. Это не слишком сложно. Тем не менее, я также хочу максимизировать число случаев, когда символ, который заменен из в генерации i + 1, является тем же символом, который был заменен в в гене i. В качестве иллюстрации, при п = 7, к = 3:
аЬс абд Abe * ABF * ABG * AFG AEG * ADG * ACG * ДСА асе * ACF * AEF ADF * ADE BDE BDF BEF BCF * BCE BCD * BCG * bdg beg * bfg * cfg ceg * cdg * cde cdf * cef def deg dfg efg
Звездообразные строки указывают случай, который я хочу максимизировать; например e, который является новым в поколении 3, abe, заменяет d, который был новым в поколении 2, abd. Кажется невозможным, чтобы это происходило в каждом поколении, но я хочу, чтобы это происходило как можно чаще.
Типичные размеры массива, которые я использую, составляют 20-30 и размер подмножества около 5-8.
Я использую нечетный язык, Icon (или фактически его производную Unicon), поэтому я не ожидаю, что кто-нибудь отправит код, который я могу использовать напрямую. Но я буду благодарен за ответы или подсказки в псевдокоде и сделаю все возможное, чтобы перевести C и т. Д. Также я заметил, что такие проблемы часто обсуждаются в терминах массивов целых чисел, и я могу, безусловно, применять решения отправленный в таких терминах к моей собственной проблеме.
Благодаря
Ким Bastin
Редактировать 15 июня 2010:
Я, кажется, попал в глубокую воду, чем я думал, и в то время как я благодарен за все ответы, не все они были актуальны. В качестве примера решения, которое НЕ является адекватным, позвольте мне опубликовать мою собственную процедуру Unicon для генерации k-арных подмножеств набора символов s в минимальном порядке изменения. Вещи, которые вам нужно знать для понимания кода: preposed * означает размер структуры, поэтому, если s является строкой, * s означает размер s (количество содержащихся в нем символов). || представляет собой операцию конкатенации строк. Предполагаемый! производит каждый элемент структуры, например. каждый символ строки, в свою очередь, последовательные проходы. И структура управления «suspend» возвращает результат процедуры, но оставляет процедуру «в ожидании» со всеми локальными переменными, чтобы новые результаты могли быть получены, если процедура вызывается в цикле.
procedure revdoor(s, k)
# Produces all k-subsets of a string or character set s in a 'revolving
# door' order. Each column except the first traverses the characters
# available to it in alphabetical and reverse alphabetical order
# alternately. The order of the input string is preserved.
# If called in a loop as revdoor("abcdefg", 3),
# the order of production is: abc, abd, abe, abf, abg, acg, acf, ace, acd,
# ade, adf, adg, aeg, aef, afg, bfg, bef, beg, bdg, bdf, bde, bcd, bce,
# bcf, bcg, cdg, cdf, cde, cef, ceg, cfg, dfg, deg, def, efg
local i
static Ctl
if /Ctl then { # this means 'if Ctl doesn't exist'
if k = 0 then return ""
Ctl := list(k, 1) # a list of k elements, each initialised to 1.
}
if Ctl[k] = 1 then {
if k = 1 then suspend !s else
every i := 1 to *s-k+1 do {
suspend s[i] || revdoor(s[i+1:0], k-1)
}
} else {
if k = 1 then suspend !reverse(s) else
every i := -k to -*s by -1 do {
suspend s[i] || revdoor(s[i+1:0], k-1)
}
}
# the following line multiplies element k of Ctl by -1 if k < size of Ctl
# (this controls the order of generation of characters),
# and destroys Ctl on final exit from the procedure.
if k < *Ctl then Ctl[k] *:= -1 else Ctl := &null
end
Обратите внимание, что выход вышеуказанной процедуры не является оптимальным в моем смысле. Одним из результатов моих исследований пока является то, что максимальная «свопинг-оценка» для списка k-арных подмножеств n элементов не меньше гребня (n-1, k), или в случае n = 7, k = 3, максимальный балл по крайней мере гребен (6, 3) = 20. Я определяю «своп-оценку» списка как количество элементов в списке, новый элемент которого заменяет элемент в предыдущем элементе, который сам был новым. У меня нет математического оборудования, чтобы доказать это, но его легко увидеть с k = 1 или k = 2.Для некоторых (п, к) немного более высокий балл можно, как и в случае п = 7, к = 3:
аЬс абд Abe ABF ABG
ACG ADG AEG AFG
EFG ДФГ CFG BFG
бек БДГ БЦЖ
BCD BCE BCF
BDF BEF
защиту CEF AEF
ADF ACF
ДСА туз
ADE
BDE CDE
CDF CDG
КЭГ
града (обменивать балл = 21)
Можно отметить, что приведенные выше список находится в «сильном порядке минимального изменения» (как слово гольфы: новый персонаж всегда находится в том же положении, что и характер, который он заменяет), что может указывать направление, которое выполняет моя собственная работа. Я надеюсь опубликовать что-то еще через несколько дней.
Kim
Я имел честь работать с иконой раз ; это потрясающий язык. 'if a polygenelubricants
Вы используете букву« n »как в« n различных символах », так и в« генерации n ». Вместо этого я предлагаю использовать «поколение i». – mathmike
Я видел один и тот же алгоритм, когда работал в проекте машинного перевода. Просто попробуйте помочь в поиске. Я не был глубоко связан с этими algs (я помню, что в нем было слово «tiling») –