We are in the process of migrating this forum. A new space will be available soon. We are sorry for the inconvenience.

kombinacje? permutacje? php c++ excel - help needed .. ;)


mariano
25-10-2006, 11:05
Chwila na google wystarczyla, zeby wyprodukowac cos takiego. Zrobilem na dole kodu szybkiego haka zmieniajacego permutacje na liste unikalnych kombinacji. Pozostawiam Ci jako cwiczenie przerobienie funkcji kpermutation() tak, zeby nie bylo to konieczne.


Kod:
#!/usr/bin/env python

SET = (1, 2, 3, 4, 5)
SUM = 11


def kpermutation(lst):
    queue = [-1]
    lenlst = len(lst)
    while queue:
        i = queue[-1]+1
        if i == lenlst:
            queue.pop()
        elif i not in queue:
            queue[-1] = i
            yield [lst[j] for j in queue]
            queue.append(-1)
        else:
            queue[-1] = i


perms = [tuple(sorted(x)) for x in kpermutation(SET)]
for subset in set(perms):
    if sum(subset) == SUM:
        print subset

Łabędź
25-10-2006, 09:40
Cytat Napisał pwsmile
Jeżeli ktoś ma jakiś pomysł, lub może już nad czymś takim myslał i ma gotowca, byłbym wdzięczny za udostępnienie.

Pozdrawiam
Na kiedy to masz?

Ja to może jestem jakiś dziwny, ale zrobił bym to rekurencyjnie. Może nie było by najszybciej, ale chyba najprościej.

pozdrawiam

pwsmile
24-10-2006, 20:21
Witam i proszę o pomoc ..

nie mogę rozgryźć następującej sprawy..

mam dane :

- x liczb (np.5 liczb i np. takie : 1 2 3 4 5 , ale może być też: 1 3 3 5 5)

- sumę którą chcę otrzymać z dodania którychś (obojętnie ilu) z danych liczb (np. suma=11)

.. i potrzebuję program / skrypt / arkusz excel, który powie mi jak Abel krowie, które liczby ze zbioru muszą być dodane, żeby utworzyły sumę jaką chcę.

Dla zbioru: 1 2 3 4 5 i danej żądanej sumy 11 byłyby to następujące możliwości:

1_2_3___5 (suma: 11)
__2___4_5 (suma: 11)

Dla zbioru: 1 3 3 5 5 i danej żądanej sumy 11 są 3 możliwości:

__3_3_5__ (suma: 11)
__3_3___5 (suma: 11)
1_____5_5 (suma: 11)

Nie jest ważne ile z liczb podanych w zbiorze złoży się na podaną sumę, jednak każda kolejna z liczb w zbiorze powtarzać się może tylko 1 raz (np. pierwsza liczba w ostatnim przykładzie (1) może byż brana pod uwagę tylko raz, czyli rozwiązaniem nie może być

1_1_1_1_1_1_1_1_1_1_1 (bo liczba 1 w zbiorze wystepuje tylko raz)

ale

liczba 5 - też w drugim przykładzie - powtórzyć się może 2 razy, bo tyle razy wystepuje w zbiorze


Super optymalnie byłoby, gdyby programik w przypadku nie znalezienia pasujących składników dających szukaną sumę, podał najbliższą możliwą kombinację w górę i najbliższą możliwą w dół ..

.. np jezeli żądaną sumą byłaby liczba 2, to mając dany zbiór jak w przykładzie drugim: 1 3 3 5 5 program nie znajdzie wprawdzie odpowiednika, bo suma żadnych ze składników w tym zbiorze nie daje liczby 2, ale wypisze:

1________ (suma: 1, reszta 1)
__3______ (suma: 3, reszta -1)
____3____ (suma: 3, reszta -1)

podobnie dla szukanej sumy 12 i tego samego zbioru: 1 3 3 5 5 pasujący odpowiednik nie zostanie znaleziony, jednak najbliższymi dodatnimi i ujemnymi wartościami będą:

1_____5_5 (suma: 11, reszta 1)
1_3___5_5 (suma: 13, reszta -1)
1___3_5_5 (suma: 13, reszta -1)




Jeżeli ktoś ma jakiś pomysł, lub może już nad czymś takim myslał i ma gotowca, byłbym wdzięczny za udostępnienie.

Pozdrawiam
pwsmile