Bir problem ve algoritma sorusu

Selamlar aşağıdaki soru bir facebook grubunda sorulmuştu uzunca uğraştım ama çözemedim. Recursion ile çözülebilir gibi gözüküyor ama recursion algoritmasını kuramadım.
Soru kısaca şu: sayılardan oluşan bir liste var ve bir tane de ayrı bir sayı var. Listedeki sayıları kullanarak toplamı, ayrı olarak verilen sayıya eşit olacak tüm sayı kombinasyonları nasıl elde edilir.

Hi Guys, I am stuck in this problem 3 days.

Given any list of numbers and a number, find all possible combinations of the numbers that add up to that number

Input: [1, 2, 3, 4, 5, 6, 7] , 6

Output: [6] , [1, 5] , [2, 4] , [3, 3] , [1, 1, 4] , [1, 2, 3] , [2, 2, 2] , [1, 1, 1, 3] , [1, 1, 2, 2] , [1, 1, 1, 1, 2] , [1, 1, 1, 1, 1, 1]

Input: [2, 3, 6, 7, 8] , 6

Output: [6] , [3, 3] , [2, 2, 2]

>>> import itertools
>>> (lambda l, i: list(filter(lambda j: sum(j)==i, (i for r in range(len(l)) for i in itertools.combinations_with_replacement(l, r)))))([2, 3, 6, 7, 8], 6)
[(6,), (3, 3), (2, 2, 2)]
>>> 

Teşekkürler cevap için ama itertools modülünü bilmiyorum henüz. Gömülü fonksiyonlar kullanmadan kendi kodlarınızla çözebilir misiniz.

Tabii:

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

def filter(f, iterable):
    for i in iterable:
        if f(i):
            yield i

def sum(iterable):
    s = 0
    for i in iterable:
        s += i
    return s

print((lambda l, i: list(filter(lambda j: sum(j)==i, (i for r in range(len(l)) for i in combinations_with_replacement(l, r)))))([2, 3, 6, 7, 8], 6))

kodunuz farklı listelerde eksik sonuç vermektedir. mesela liste = [1, 2, 3, 4, 5, 6] ve sayı =6 ile denediğimde [1, 1, 1, 1, 1, 1] sonucunu üretmemektedir. Diğer kodda da aynı eksiklik mevcut.

Düzelttim:

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

def filter(f, iterable):
    for i in iterable:
        if f(i):
            yield i

def sum(iterable):
    s = 0
    for i in iterable:
        s += i
    return s

def map(f, iterable):
    for i in iterable:
        yield f(i)

def unpack(iterable):
    for i in iterable:
        yield from i

print(
    (lambda l, i: list(
        filter(lambda j: sum(j)==i,
                   unpack(combinations_with_replacement(l, r) for r in range(len(l)+1))
               )
        )
     )([1, 2, 3, 4, 5, 6], 6)
    )

Bu da benden olsun:

def possible_combination_sum(numbers: list, total: int):
    # combinations that will be calculated and processed
    combinations = [()]

    # final result. every member's sum equals to total
    result = []

    finished = False

    while not finished:
        finished = True

        # updated combination list for new combinations
        updated = []

        for combination in combinations:
            current_sum = sum(combination)

            if current_sum == total:
                # append it to the result without making a process on it
                result.append(combination)

            elif current_sum < total:
                # add new numbers to the current sum and append
                # these new combinations to the updated list
                for new_number in numbers:
                    if current_sum + new_number <= total and \
                            (len(combination) == 0 or new_number >= combination[-1]):
                        updated.append(combination + (new_number,))

                finished = False

        # update actual combination list
        combinations = updated

    return result

Kodu detaylı açıklayabilir misiniz

En başta elimizde boş bir kombinasyon listesi var.

Bir de en sonda sonuçları koyacağımız sonuç listesi. Bu listenin içindeki tuple’ların içindeki sayıların toplamı total değişkenine eşit olacak.

Ve döngünün devam edip etmemesi gerektiği değerini taşıyan finished (bitti) değişkenimiz var.

Döngü not finished ifadesi False değer ifade edene kadar devam edecek. Yani finished değişkeni False ise döngü tekrar çalışıyor. Döngü başladıktan sonra hemen finished değişkenine True değer vermemizin sebebi ilerde bazı kontrol blokları ile bunu değiştirebilmemiz. Yani her döngü başında finished değişkeni True değerini alıyor, eğer döngü gövdesinin içinde sonradan bunun değeri False olarak değiştirilmezse döngü bitecek.

Güncellenmiş kombinasyonları koyacağımız updated listemizi oluşturup boş bir listeye eşitliyoruz.

Bu for döngüsünde ise önceden hesapladığımız kombinasyonların bulunduğu combinations listesinin içinde dolaşıyoruz. Her iterasyonda combination değişkene yeni bir değer atanıp döngü tekrar çalıştırılıyor. Ta ki combination değişkeni combinations listesindeki tüm değerleri alana kadar. Her döngü başlangıcında da combination listesi içindeki değerlerin toplamını hesaplayıp current_sum (şimdiki toplam) değişkenine bu değeri veriyoruz.
Eğer combination = [1, 1, 1, 1, 1] ise current_sum = 5 olacak.

Burda current_sum değişkeninin total’a eşit olup olmadığını kontrol ediyoruz. Eğer eşitse, bu listeyle yapacağımız herhangi bir hesaplama kalmamış demektir. Örneğin combination = [1, 1, 1, 1, 1, 1] ise ve total = 6 ise bu liste ile yapacağımız herhangi bir işlem kalmamış demektir. Yani bu değeri result adındaki sonuç listemize ekleyebiliriz.

Eğer current_sum değişkenimiz total’a eşit değil de total’dan küçükse bu kod bloğu çalışacak. Bu durumda bu listeyle işimiz bitmemiş demektir.

Burada new_number yeni sayı değişkenini numbers içinde gezdiriyoruz. numbers değerimiz fonksiyonun aldığı bir değer ve sorudaki örneklerdeki [1, 2, 3, 4, 5, 6, 7] ve [2, 3, 5, 6, 7, 8] listelerini temsil ediyor. new_number değerimizi bu listelerin içerisinde gezdiriyoruz ki önceki döngülerde hesapladığımız combinations listesi içindeki toplamı henüz total’a eşit olmayan combinationdeğerlerinin sonuna numbers listesi içindeki uygun sayıları ekleyip yeni oluşan listeleri updated listesine ekleyebilelim.

Burada iki farklı kontrol yapıyoruz.

  • Eğer bu sayıyı şuanki "combination" listesine eklersek listenin yeni toplamı olması gereken "total" değerinden küçük veya eşit olur mu?
    Yani combination = [1, 2], total = 4 ve new_number = 4 ise bunu listeye ekleyemeyiz çünkü bunun sonucunda yeni listemizin toplamı total’dan büyük olur.
  • Yeni ekleyeceğimiz sayımız listedeki en son sayıdan büyük veya eşit mi?
    Bu kontrolü yapmamızın nedeni çıktı olarak [1, 3, 5] ve [1, 5, 3] olarak iki farklı değer almak istememiz. Bunu önlemek içinde yeni ekleyeceğimiz sayının listenin son elemanından büyük veya eşit olması koşulunu koyuyoruz. Böylece çıktımızda sadece [1, 3, 5] kombinasyonu yer alacak. Fakat burada new_number sayısını direkt olarak combination’ın son elemanı ile karşılaştıramayız çünkü eğer combination’ın içinde bir sayı değeri yoksa listede olmayan bir elemana erişmeye çalıştığımız için bir hata alırız. Bunu önlemek için Yeni sayı listenin son elemanından büyük veya küçük mü? demek yerine Listenin uzunluğu 0'a eşit mi VEYA yeni sayı listenin son elemanından büyük mü? diyoruz.

Eğer iki koşul da sağlanıyorsa combination’a içerisinde sadece new_number adlı sayımızın bulunduğu bir tuple ile birleştirip güncellenmiş listeye ekliyoruz. Örneğin:

combination = (1, 2, 2)
new_number = 4
combination + (new_number,) => (1, 2, 2) + (4,) => (1, 2, 2, 4)

finished (bitti) değişkenimize False değer veriyoruz ki döngü devam etsin. Eğer current_sum < total ifadesi hiçbir zaman True değer döndürmezse yapacak bir işlemimiz kalmamış demektir, yani while not finished: döngüsünü bitirebiliriz, ama bu if bloğunun içine girdiysek bu, döngüye devam etmemiz gerekiyor demektir yani finished’ı False yapabiliriz.

while döngüsünün sonunda combinations (kombinasyonlar) değişkenini updated (güncellenmiş) değişkenine eşitliyoruz ki bir sonraki döngü tekrarında aynı combination listesiyle işlem yapıp önceki tekrarda yaptığımız aynı şeyi tekrar etmeyelim, yeni değerler ile işlemler yapalım

En sonda da sonuç değişkenini döndürüyoruz.

anladım çok teşekkürler