Тема: Комбінаторика (теорія, методи, модулі і т.п.)

Пан funivan запостив тему про новорічну гру для кодерів http://replace.org.ua/topic/5985/
Я в таких речах бачу чудову можливість підучити якусь нову мову, наразі бавлюся з Ruby. Деякі задачі довелося робити "брутфорсом", благо в ruby є кілька встроєних методів типу permutation, combination. (у Python є чудова ліба - itertools, це не реклама)
Але для деяких задач цього недостатньо, тому довелося писати свій модуль, можливо комусь допоможе:

Прихований текст
module Itertools

    def Itertools.combination_iter(items, value_range)
        # Example:
        #
        # items = ["a", "b"], value_range = [1, 2]
        # combinations:
        # [{"a":1, "b":1}, {"a":2, "b":1}, {"a":1, "b":2}, {"a":2, "b":2}]

        combination = Hash[items.zip([value_range[0]] * items.length)]
        yield combination

        has_next_combination = true
        while has_next_combination
            next_combination = false
            index = 0
            while index < items.length and not next_combination
                cur_value = combination[items[index]] + 1
                if cur_value > value_range[1] then
                    combination[items[index]] = value_range[0]
                    index += 1
                elsif
                    combination[items[index]] = cur_value
                    next_combination = true
                    yield combination
                end
            end
            has_next_combination = next_combination
        end
    end

    def Itertools.combination_with_total_sum(items, total)
        # Example:
        #
        # items = ["a", "b"], total_sum = 3
        # combinations:
        # [{"a":0, "b":3}, {"a":1, "b":2}, {"a":2, "b":1}, {"a":3, "b":0}]
        if items.length == 1 then
            return [{items[0] => total}]
        else
            result = []
            (0..total).each do |i|
                combination = {items[0] => i}
                sublist = combination_with_total_sum(items[1..-1], total-i)
                sublist.each do |item|
                    combination.update(item)
                    result.push(combination.clone)
                end
            end
            return result
        end
    end

end

__END__

def test
    input_items = ["a", "b", "c"]
    input_range = [1, 3]
    output = [{"a"=>1, "b"=>1, "c"=>1},
              {"a"=>2, "b"=>1, "c"=>1},
              {"a"=>3, "b"=>1, "c"=>1},
              {"a"=>1, "b"=>2, "c"=>1},
              {"a"=>2, "b"=>2, "c"=>1},
              {"a"=>3, "b"=>2, "c"=>1},
              {"a"=>1, "b"=>3, "c"=>1},
              {"a"=>2, "b"=>3, "c"=>1},
              {"a"=>3, "b"=>3, "c"=>1},
              {"a"=>1, "b"=>1, "c"=>2},
              {"a"=>2, "b"=>1, "c"=>2},
              {"a"=>3, "b"=>1, "c"=>2},
              {"a"=>1, "b"=>2, "c"=>2},
              {"a"=>2, "b"=>2, "c"=>2},
              {"a"=>3, "b"=>2, "c"=>2},
              {"a"=>1, "b"=>3, "c"=>2},
              {"a"=>2, "b"=>3, "c"=>2},
              {"a"=>3, "b"=>3, "c"=>2},
              {"a"=>1, "b"=>1, "c"=>3},
              {"a"=>2, "b"=>1, "c"=>3},
              {"a"=>3, "b"=>1, "c"=>3},
              {"a"=>1, "b"=>2, "c"=>3},
              {"a"=>2, "b"=>2, "c"=>3},
              {"a"=>3, "b"=>2, "c"=>3},
              {"a"=>1, "b"=>3, "c"=>3},
              {"a"=>2, "b"=>3, "c"=>3},
              {"a"=>3, "b"=>3, "c"=>3}]

    result = []
    Itertools.combination_iter(["a", "b", "c"], [1, 3]) do |combination|
        result.push(combination.clone)
    end
    puts "Test combination_iter: #{output == result ? 'passed' : 'failed'}"

    input_items = ["a", "b", "c"]
    input_total = 5
    output = [{"a"=>0, "b"=>0, "c"=>5},
              {"a"=>0, "b"=>1, "c"=>4},
              {"a"=>0, "b"=>2, "c"=>3},
              {"a"=>0, "b"=>3, "c"=>2},
              {"a"=>0, "b"=>4, "c"=>1},
              {"a"=>0, "b"=>5, "c"=>0},
              {"a"=>1, "b"=>0, "c"=>4},
              {"a"=>1, "b"=>1, "c"=>3},
              {"a"=>1, "b"=>2, "c"=>2},
              {"a"=>1, "b"=>3, "c"=>1},
              {"a"=>1, "b"=>4, "c"=>0},
              {"a"=>2, "b"=>0, "c"=>3},
              {"a"=>2, "b"=>1, "c"=>2},
              {"a"=>2, "b"=>2, "c"=>1},
              {"a"=>2, "b"=>3, "c"=>0},
              {"a"=>3, "b"=>0, "c"=>2},
              {"a"=>3, "b"=>1, "c"=>1},
              {"a"=>3, "b"=>2, "c"=>0},
              {"a"=>4, "b"=>0, "c"=>1},
              {"a"=>4, "b"=>1, "c"=>0},
              {"a"=>5, "b"=>0, "c"=>0}]

    result = Itertools.combination_with_total_sum(["a", "b", "c"], 5)

    puts "Test combination_with_total_sum: #{output == result ? 'passed' : 'failed'}"
end

test

Також бачимо, що другий метод реалізовано через рекурсію, тому, на жаль, не зміг скористатися yield, щоб утворити рубівський енумератор (якщо не поплутав термін). Можливо, хтось з вас придумає кращу реалізацію, прошу поділитися.

Подякували: leofun01, A.N.Onim, FakiNyan3

2 Востаннє редагувалося Master_Sergius (31.12.2015 12:19:59)

Re: Комбінаторика (теорія, методи, модулі і т.п.)

Хто ще не пройшов день 17 в тій грі і хоче це зробити самостійно, то не заглядуйте в спойлер :)

Задачу зробив не повним перебором, але, на жаль, на великих числах воно все одно довго думає.
Отож, спершу алгоритм (спойлер #1)

Прихований текст

Нехай у нас є контейнери - [2,3,5], потрібно знайти усі способи як скласти 5

Пробуємо складати усі суми від 1 до 5:
1: скласти неможливо, нічого не пишемо
2: складається готовим контейнером, маємо комбінацію [2]
3: як і попереднє - [3]
4: не складається
5: Тут детальніше опишу, робимо прохід по кожному контейнеру (це робиться для кожної суми, просто в попередніх нема що описувати)
   1) контейнер 2, ми можемо отримати 5, якшо взяти контейнер 2 і докласти його до суми 3, а сума 3 у нас складається, отже:
        комбінація_1 - [3, 2]
   2) контейнер 3, відповідно докладаємо до суми 2, маємо комбінація_2 - [2, 3]
   одразу робимо перевірку дублікатів - [3,2] - те саме, що й [2,3], отже цю комбінацію не додаємо у список
   3) контейнер 5 - комбінація [5], дублікатів немає, на виході маємо [[3, 2], [5]]

Отже, відповідь буде - 2, двома способами можна скласти суму 5.

Тепер код до даного алгоритму (спойлер #2):

Прихований текст
def get_containers_combinations(containers, total)
    # Example:
    #
    # containers = [20, 15, 10, 5, 5], total = 25
    # result:
    # [15, 10]
    # [20, 5] (the first 5)
    # [20, 5] (the second 5)
    # [15, 5, 5]

    def add_container(cntr_index, containers, current_sum, combinations)
        # Helper function to handle combinations
        #
        # Example:
        #
        # containers = [2, 3, 5] (indexes - 0, 1, 2)
        # possible combinations:
        #       {2 => [[0]], 3 => [[1]],
        #        5 => [[2], [0, 1]], 7 => [[0, 2]],
        #        8 => [[1, 2]], 10 => [[0,1,2]]}
        if not combinations.has_key? current_sum
            combinations[current_sum] = []
        end
        added = false
        if containers[cntr_index] == current_sum
            combinations[current_sum].push([cntr_index])
            added = true
        elsif
            # find all combinations to which we can add this container
            avail = combinations[current_sum - containers[cntr_index]]
            avail.each do |comb| # each combination is type of Array
               if not comb.member? cntr_index
                   new_combination = comb.clone.push(cntr_index)
                   # check for possible duplicates
                   dup = false
                   combinations[current_sum].each do |item|
                       if item.sort == new_combination.sort
                           dup = true
                       end
                   end
                   if not dup
                       combinations[current_sum].push(new_combination)
                   end
                   added = true # even if dup, because it already has this
               end
            end # avail.each
        end
        added
    end

    biggest = containers.max # uses only for saving system resources

    # try to find combinations for each sum, from 1 to total
    # each next sum's combination may be based on previous sum's
    sums = [false] * (total + 1)
    combinations = {}
    (1..total).each do |current_sum|
        containers.each_index do |i|
            if containers[i] == current_sum then
                sums[current_sum] = true
                add_container(i, containers, current_sum, combinations)
            elsif containers[i] < current_sum and
                  sums[current_sum - containers[i]] then
                added = add_container(i, containers, current_sum, combinations)
                sums[current_sum] = added
            end
        end
        # remove no longer needed combinations to save system resources
        (1..current_sum - biggest).each do |combs|
            combinations.delete(combs)
        end
    end
    # build result, because combinations stores containers by indexes
    result = []
    combinations[total].each do |comb|
        result.push(comb.map { |i| containers[i] })
    end
    result
end

def get_number_of_combinations(containers, total)
    all = get_containers_combinations(containers, total)
    all.length
end

def doit
    containers = []
    fin = File.new("day17_input.txt", 'r')
    for line in fin
        containers.push(line.to_i)
    end
    fin.close

    puts get_number_of_combinations(containers, 150)
end

doit

__END__

def test
    containers = [20, 15, 10, 5, 5]
    total = 25

    all = get_containers_combinations(containers, total)
    print all
end

test

Отож, на доволі потужному компі дана задача (сума 150) рахується майже 7 хвилин, на моєму слабенькому нетбуку - до 20 хвилин. Хто має пропозиції як поліпшити алгоритм, код, пишіть, не соромтеся.

Подякували: leofun011

3

Re: Комбінаторика (теорія, методи, модулі і т.п.)

ааа, то це гра про код, а я думав, що там треба вручну робити все. Дійсно, непоганий спосіб розібратись з новою мовою, спробую зробити то всьо з нуля, на бідоні

Подякували: leofun011

4 Востаннє редагувалося koala (31.12.2015 14:09:53)

Re: Комбінаторика (теорія, методи, модулі і т.п.)

Ще не дістався 17, але чому б ні?

Суттєва частина:
bottles = [int(size) for size in inp.split('\n')]
def calculateVolume(bottles, count):
    return sum( bottles[j] for j in range(len(bottles)) if (count & (1<<j)) !=0 )

def calculateCombinations(bottles, volume):
    return sum( 1 for i in range(2**len(bottles)) if calculateVolume(bottles,i)==150 )
print( calculateCombinations(bottles, 150) )

Для моїх вхідних даних вийшло 4.1340265 секунди на Core i3-4150@3.50GHz
За бажання можна все в один рядок запхати :)

Подякували: Master_Sergius, leofun012

5

Re: Комбінаторика (теорія, методи, модулі і т.п.)

Пане koala, мушу визнати: Ви - "маг і чародєй"!
Але, звідки? Звідки Ви взяли цей алгоритм? А також, по яких ресурсах ходите, щоб оволодіти такою технікою побітових операцій?

п.с. ваш код на python, а тема ruby, але фіг з ним - це круто!

6 Востаннє редагувалося koala (31.12.2015 16:00:09)

Re: Комбінаторика (теорія, методи, модулі і т.п.)

Та тут чиста дискретна математика (і півгодинки на те, щоб її нормально запхати в формулу).
Ідея така: нам треба утворити всі підмножини з множини (наприклад, з [0,1,2] -> [],[0],[1],[2],[0,1],[0,2],[1,2],[0,1,2]) і вибрати з них потрібні. Це еквівалентно тому, що перебрати всі комбінації (належить, не належить) для кожного з елементів множини. Так, підмножині [0,2] відповідає комбінація [належить, не належить, належить]. Всього таких комбінацій, очевидно, 2потужність множини. Далі я трохи поексперементував зі списком із булевих значень, але швидко стало очевидно, що я роблю вже давно реалізовані дії з числами. Потім спробував утворювати такі булеві масиви з чисел, теж не дуже вдало, зате вже схопив ідею. Трохи її відлагодив, почистив код - і прошу. Так що ніякої магії.

Подякували: Master_Sergius, leofun012

7

Re: Комбінаторика (теорія, методи, модулі і т.п.)

Якось теж цікавився, тож..
Реалізації комбінаторики на Java, Python, Haskell, C++, JavaScript
http://bit.ly/1kw2uEg

Подякували: leofun011

8

Re: Комбінаторика (теорія, методи, модулі і т.п.)

koala написав:

Та тут чиста дискретна математика (і півгодинки на те, щоб її нормально запхати в формулу).
...
Потім спробував утворювати такі булеві масиви з чисел, теж не дуже вдало, зате вже схопив ідею. Трохи її відлагодив, почистив код - і прошу. Так що ніякої магії.

І все ж, щоб думати в цій площині, потрібно вже по ній пройтися вдосталь. Ось і питання - звідки? Підкиньте ресурси, якщо не шкода :)

Все ж, це не потрібне у моїй роботі, але чим чорт не жартує :)

9

Re: Комбінаторика (теорія, методи, модулі і т.п.)

Master_Sergius написав:
koala написав:

Та тут чиста дискретна математика (і півгодинки на те, щоб її нормально запхати в формулу).
...
Потім спробував утворювати такі булеві масиви з чисел, теж не дуже вдало, зате вже схопив ідею. Трохи її відлагодив, почистив код - і прошу. Так що ніякої магії.

І все ж, щоб думати в цій площині, потрібно вже по ній пройтися вдосталь. Ось і питання - звідки? Підкиньте ресурси, якщо не шкода :)

Все ж, це не потрібне у моїй роботі, але чим чорт не жартує :)

нумо зі мною математику вивчати, пан koala допомагає в цьому

10

Re: Комбінаторика (теорія, методи, модулі і т.п.)

FakiNyan написав:

нумо зі мною математику вивчати, пан koala допомагає в цьому

Ну Я не сказав би, що в мене проблеми з математикою, але тут діло в специфічних алгоритмах і підходах, це більше різного роду "олімпіадні задачі". Тому й прошу підкинути відповідних ресурсів.

11

Re: Комбінаторика (теорія, методи, модулі і т.п.)

Знаєте, мені тут дуже важко щось порадити. Конкретно в цьому випадку - це банальна дискретна математика з інститутського курсу плюс примітивні знання бітової арифметики. Поки я це придумував, трохи гуглив і наштовхувався на формули на кшталт i^~(i+1) - і таке мені важко сходу зрозуміти, треба обдумувати. Моя формула значно простіша: це просто перевірка на встановлення i-го біта.

12

Re: Комбінаторика (теорія, методи, модулі і т.п.)

 i^~(i+1)

i =

10101010101111111
         ^

i + 1 =

10101010110000000
         ^

i^~(i+1) =

11111111100000000
         ^

Подякували: leofun011