Python, problem z algorytmem

Question

Witam!
Zaczynam swoją przygodę z programowaniem i potrzebuję pomocy w zadaniu, ponieważ zaciąłem się w jednym punkcie i nie mam pomysłu jak inaczej podejść do problemu.
Treść brzmi następująco:
Dla zadanego zbioru liczb wypisz jego najmniej liczny podzbiór, którego suma jest większa niż suma pozostałych elementów tego zbioru.
Program wypisuje możliwe podzbiory, ale przy większej ilości wylosowanych elementów gubi niektóre z nich.
Będę wdzięczny jeśli ktoś postanowi mi pomóc.

import random
def randTab(n,tab):

    for i in range(n):
        tab.append(random.randint(0,10))

    print(tab)

mainList=[]
sum1=[]
sum2=[]
temp=0
length=int(input("Podaj dlugosc tablicy do wylosowania "))
randTab(length,mainList)
mainList.sort(reverse=True)
sum2.extend(mainList)

for i in range(0,length-1):
    sum1.append(mainList[i])
    sum2[i]=0
    if(sum(sum1)>sum(sum2)):
        print(sum1)
        break

for j in range(i+1,length):

    temp=sum1[i]
    sum1[i]=sum2[j]
    sum2[j]=temp
    if(sum(sum1)>sum(sum2)):
        print(sum1)

 

Comments

Hmm, chyba nie rozumiem do czego ma być ta druga pętla. Czemu nie wystarczy samo to?
 

 
for i in range(0,length-1):
    sum1.append(mainList[i])
    sum2[i]=0
    if(sum(sum1)>sum(sum2)):
        print(sum1)
        break

I chyba zgubiłeś tam poziom wcięcia :)

---

Ten fragment w wielu przypadkach wypisze tylko jeden możliwy podzbiór. Głównym problemem jest to że program powinien wypisywać wszystkie możliwe kombinacje takich podzbiorów o jednakowej dlugości np. dla danych wejściowych [2,4,1,3,9,0,3] wyjściem jest [4,9],[3,9]. Druga pętla jest moim desperackim podejściem do tego problemu  jakoś działa ale przy większej ilości danych wejściowych gubi dużą część kombinacji. 

---

Druga pętla nie pomoże bo może być dużo więcej takich podzbiorów niż dwa :)

Mój kod znajduje wszystkie, ale przechodzi przez wszystkie permutacje listy i działa cholernie wolno.

---

Całkowicie to rozumiem i dzięki za pomoc. Sam próbowałem to rozwiązać w taki sposób ale ilość możliwych kombinacji drastycznie zwiększała się przy większych listach i odpuściłem sobie bo chyba nie tak to miało wyglądać. Jedynym rozwiązaniem jest zwiększenie zakresu losowania liczb, wtedy różnice pomiędzy sumami są na tyle duże że program nabiera troszeczkę rozpędu  

---

Problem wydaje się prosty, ale taki super prosty to nie jest. Skąd jest to zadanie?

Jeszcze spróbuje wykonać kolejną wersję, bez permutacji i itertools, mam pewien pomysł, w najbliższych dniach podeślę.

Mam nadzieję, że jeszcze ktoś inny przedstawi swoją koncepcję, inne rozwiązanie.

Answer 1

Spróbuję pomóc. Tylko czy liczby mogą się powtarzać w tabeli i czy można ja sobie posortować narastająco??

------

Zrobiłem programik ale on jest baaaaaaarrrrrdzo powolny, sugeruje nie odpalać dla większych list niż 10-13 elementów :)

import random
import itertools


def randTab(n):
    tab = list()
    for i in range(n):
        tab.append(random.randint(0, 20))
    return tab


t = randTab(8)
#t = [2, 4, 1, 3, 9, 0, 3]
print(t)

candidates = []
shortest_length = 1000

for t0 in itertools.permutations(t, len(t)):
    t = t0
    for i in range(len(t)):
        for j in range(1, len(t)):
            if i + j <= len(t):
                t1 = t[i:i + j]
                t2 = t[0:i] + t[i + j:]
                if sum(t1) > sum(t2) and len(t1) <= shortest_length:
                    candidates.append(list(t1))
                    shortest_length = len(t1)


result = [t for t in candidates if len(t) == shortest_length]
result2 = list()
for r in result:
    r.sort()
    if r not in result2:
        result2.append(r)
        print(r)

UWAGA! Działa powoli, dobry do zamulenia komputera! ;) Spróbuje go poprawić, ale póki co wysyłam wersję taką jaka jest.

Sprawę skomplikowało, że jest to najmniej liczny podzbiór liczb z listy, a nie najmniej liczny podzbiór kolejnych liczb z listy, stąd permutacje z itertools :) Z kolejnymi liczbami poszło szybciej i lepiej, ale niestety to nie to zadanie :)

Ciekaw jestem innych rozwiązań kolegów !!! Chętnie zobaczę lepsze rozwiązania....

 

Comments

Wersja v 2.0 :) 

Działa milion razy lepiej, ale nie obyło się bez pomocy modułu itertools (tym razem kombinacje zamiast permutacji). Działa naprawdę szybko, jestem z grubsza zadowolony :)

# ver: 2.0 (11/11/2021), (C)opyright: reaktywny

import random
import itertools


def rand_tab(n):
    tab = list()
    for i in range(n):
        tab.append(random.randint(0, 20))
    return tab


t0 = rand_tab(random.randint(5, 15))
#t0 = [2, 4, 1, 5, 6, 1, 3]
#t0 = [20, 18, 19, 14, 17, 12, 5, 4, 3, 3, 1, 0]
#t0= [2, 4, 1, 3, 9, 0, 3]
t0.sort(reverse=True)
print(f"\n\nLista z liczbami: <{t0}>.\n\n")

result = list()
t = t0


def ffss(idx_f, idx_t, lll):
    while True:
        if idx_f > len(t)-1 or idx_t >= len(t):
            return -1
        t1 = t[idx_f:idx_t]
        t2 = t[:idx_f] + t[idx_t:]
        if sum(t1) > sum(t2):
            t1.sort()
            if t1 not in result and len(t1) <= lll:
                result.append(t1)
            return len(t1)
        else:
            idx_t += 1
    return -1


def fnss(ss, wl):
    sum_ss = sum(ss)
    for val in ss:
        wl.remove(val)
    sum_wl = sum(wl)
    if sum_ss > sum_wl:
        ss = list(ss)
        ss.sort()
        if ss not in result:
            result.append(ss)


length = ffss(0, 1, 1000)
for comb in itertools.combinations(t[:-1], length):
    fnss(comb, t.copy())

for r in result:
    print(f"Podzbiór: {r} i jego suma: {sum(r)}.")

 

Ten program nie jest "oczyszczony" (parę rzeczy jest do wyrzucenia), ale działa dobrze.