Перебор целочисленных массивов с фиксированной суммой в Julia - PullRequest
Новая
       21

Перебор целочисленных массивов с фиксированной суммой в Julia

2 голосов
/ 19 марта 2019

Я ищу алгоритм для перебора всех массивов длины n, чьи записи являются целыми числами от 0 до d и чья сумма k * d.Было бы еще лучше, если бы был способ сделать это с помощью встроенных функций Julia и итераторов.Алгоритм должен быть нерекурсивным и эффективно использовать память, так как я надеюсь использовать его для разумных значений n.

Для небольших значений n, d и k я записал все такие массивы в лексикографическом выражении.упорядочение, но я не смог придумать код для перебора всех таких массивов.

1 Ответ

2 голосов
/ 19 марта 2019

Я думаю, что это должно работать, но это требует Combinatorics.jl и ResumableFunctions.jl

using Combinatorics, ResumableFunctions
@resumable function gen_all(n, k, d)
    for x in partitions(k*d + n, n)
        x = x .- 1
        if all(x .<= d) 
            ys = Set(permutations(x))
            for y in ys
                @yield y
            end
        end
    end
end


for ga in gen_all(5, 2, 2)
    println(ga)
end

дает 

[2, 0, 0, 2, 0]
[2, 0, 0, 0, 2]
[0, 0, 2, 2, 0]
[0, 2, 2, 0, 0]
[2, 0, 2, 0, 0]
[0, 2, 0, 2, 0]
[2, 2, 0, 0, 0]
[0, 0, 0, 2, 2]
[0, 0, 2, 0, 2]
[0, 2, 0, 0, 2]
[0, 2, 0, 1, 1]
[0, 1, 1, 0, 2]
[0, 1, 2, 0, 1]
[0, 1, 1, 2, 0]
[2, 1, 1, 0, 0]
[2, 1, 0, 0, 1]
[0, 0, 1, 1, 2]
[1, 2, 1, 0, 0]
[1, 2, 0, 0, 1]
[0, 1, 2, 1, 0]
[0, 1, 0, 1, 2]
[1, 0, 0, 1, 2]
[0, 2, 1, 1, 0]
[2, 0, 0, 1, 1]
[1, 0, 2, 0, 1]
[1, 2, 0, 1, 0]
[0, 1, 0, 2, 1]
[2, 0, 1, 0, 1]
[0, 2, 1, 0, 1]
[1, 0, 1, 2, 0]
[0, 0, 1, 2, 1]
[1, 0, 0, 2, 1]
[2, 1, 0, 1, 0]
[1, 1, 0, 0, 2]
[1, 0, 2, 1, 0]
[1, 0, 1, 0, 2]
[1, 1, 0, 2, 0]
[0, 0, 2, 1, 1]
[2, 0, 1, 1, 0]
[1, 1, 2, 0, 0]
[1, 1, 1, 0, 1]
[1, 1, 0, 1, 1]
[1, 0, 1, 1, 1]
[1, 1, 1, 1, 0]
[0, 1, 1, 1, 1]
...