• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Python, problem z algorytmem

VPS Starter Arubacloud
+1 głos
475 wizyt
pytanie zadane 9 listopada 2021 w Python przez PeWeX47 Nowicjusz (130 p.)

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)

 

komentarz 9 listopada 2021 przez adrian17 Ekspert (344,100 p.)
edycja 9 listopada 2021 przez adrian17

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 :)

2
komentarz 9 listopada 2021 przez PeWeX47 Nowicjusz (130 p.)

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 frown jakoś działa ale przy większej ilości danych wejściowych gubi dużą część kombinacji. 

komentarz 10 listopada 2021 przez reaktywny Nałogowiec (40,650 p.)
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.
komentarz 10 listopada 2021 przez PeWeX47 Nowicjusz (130 p.)

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 laugh 

komentarz 10 listopada 2021 przez reaktywny Nałogowiec (40,650 p.)
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.

1 odpowiedź

0 głosów
odpowiedź 10 listopada 2021 przez reaktywny Nałogowiec (40,650 p.)
edycja 10 listopada 2021 przez reaktywny

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....

 

komentarz 11 listopada 2021 przez reaktywny Nałogowiec (40,650 p.)
edycja 11 listopada 2021 przez reaktywny

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.

Podobne pytania

0 głosów
0 odpowiedzi 212 wizyt
pytanie zadane 19 października 2021 w C# przez Vales Nowicjusz (120 p.)
0 głosów
1 odpowiedź 117 wizyt
pytanie zadane 9 grudnia 2019 w Rozwój zawodowy, nauka, praca przez Sawik Nowicjusz (120 p.)
0 głosów
2 odpowiedzi 331 wizyt
pytanie zadane 19 lutego 2021 w Rozwój zawodowy, nauka, praca przez kirimoto Nowicjusz (160 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...