x-kokoisten sarjojen kombinaatioiden tulostus alkiojoukosta (Pseudo)? [RATKAISTU

[Jere Sumell]

Tämän kaltainen aivojumppaa minulle / ongelma tässä alkoi viime yönä 4:10 herättyäni kolmen tunnin yöunilta.

En ole edes yrittänyt vielä implementoida millään ohjelmointikielellä tätä käytännössä, pitää ensin saada abstraktilla tasolla pseudokielellä toimimaan teoriassa.

Tässä nyt paras, mihin olen jäänyt jumiin:

Koodia: [Valitse]

MODULE SARJOITA (A [], LKM):
ualkiot = "";
x = A.LENGTH;
laskuri = x;
DO:
IF (X-1 >=0):
FOR (Y=X;Y<LKM;Y--):
ualkiot+ = A[y-1]
ELSE:
PRINT (ualkiot)
x--;
laskuri--;
WHILE ((x-lkm >=0))
MODULE END
Esimerkiksi jos syöteparametrit ovat seuraavat:
A[] = {1,2,3,4,5,6} ja LKM 4
niin tulosteena pitäisi tulla seuraavat numerosarjat kombinaatiot kaikki mahdolliset:

1,2,3,4
1,2,3,5
1,2,3,6
2,3,4,5
.....
3,4,5,6

Osaisiko joku minua viisaampi auttaa tässä?  Varmasti tällä palstalla moni on käynyt tämän itsekseen joskus ohjelmoidenkin ihan käytännössä ohjelmoinutkin vastaavan?

[UnelmaIkuisestaOnnesta]

Minulla on sinulle arvoitus.

Miten alla oleva pseudokoodi tuottaa oikean vastauksen?

Mietin sitä täällä itse. Tuo tehtävä oli kiehtova, mutta se ylitti omat kykyni, joten kysyin lopulta neuvoa tekoälyltä ja sain vastaukseksi toimivan Python koodin. Muutin sen ensin kommentoiduksi ja sitten pseudokoodiksi ja olen nyt tuijottanut sitä miettien syntyjä syviä.

Koodia: [Valitse]

ALIOHJELMA KOMBINAATIOT(A [], LKM):
    JOS LKM > A.PITUUS:
        PALAUTA TYHJÄLISTA
    JOS LKM == 0:
        PALAUTA LISTA JONKA SISÄLLÄ ON TYHJÄ LISTA
    KOMBINAATIOT = TYHJÄLISTA
    KÄY LÄPI i:n ARVOT NOLLASTA A:n PITUUTEEN -1 ASTI
    A1 = A.OTA_LISTALTA_i_ENSIMMÄISTÄ_ALKIOTA_UUDEKSI_LISTAKSI()
    LKM1 = LKM - 1
    OSAKOMBINAATIOT = KOMBINAATIOT(A1, LKM1)
    KÄY LÄPI OSAKOMBINAATIOT JOS SE EI OLE TYHJÄ LISTA
            OSAKOMBINAATIO.LISÄÄ_LISTALLE(A[i])
    KOMBINAATIOT.LISÄÄ_LISTALLE(OSAKOMBINAATIO)
    PALAUTA KOMBINAATIOT

Sama Python koodina.

Koodia: [Valitse]

"""
    Kombinaatioita listasta luova aliohjelma.
   
    koko: Kuinka monta alkiota kombinaatiossa on.
    lista: Mistä listasta luodaan kombinaatiot.

    Aliohjelma on rekursiivinen, eli se kutsuu itse itseään.
"""

def kombinaatiot(lista, koko):
    if koko > len(lista): # 1.
        return []
    if koko == 0: # 2.
        return [[]]
    kombinaatiolista = []
    for i in range(0, len(lista)):
        # Jokaisella rekursiokerralla listalta jää aina pois
        # sen viimeinen alkio, jota ei käsitellä lainkaan.
        # Lisäksi kombinaatioiden alkioiden määrä vähenee yhdellä.
        for kombinaatio in kombinaatiot(lista[:i], koko-1):
            # Rekursiivinen funktiokutsu toimii näin. Muuttujien arvot
            # ovat tässä tämän suorituskerran arvoja, eivät kutsulle
            # annettuja arvoja.
            #   1. Jos i < koko, tätä ei suoriteta
            #   2. Koolla 1 kombinaatiolistalla on alkiona pelkkä lista[i]
            #   3. Koolla >1 yhtä pienemmän koon listaan lisätään alkioksi lista[i]
            kombinaatiolista.append(kombinaatio + [lista[i]])
    return kombinaatiolista # 3.

lista = ['a','b','c','d','e','f']
kombinaationkoko = 5
print("Ohjelma laskee", kombinaationkoko, "alkioiset kombinaatiot listalle", lista)
print("VASTAUS")
for kombinaatio in sorted(kombinaatiot(lista, kombinaationkoko)):
print(kombinaatio)

PSST.

Tuossa sinun kirjoittamassasi pseudokoodissa on jotain hämärää. Vääntelin sitä miten päin tahansa, niin aina kun sen yrittää muuttaa oikeaksi koodiksi, se joko jumittuu ikuiseen silmukkaan tai sitten ei tulosta mitään, tai sitten tulostaa vain kaikki taulukon alkiot. Silti tuossa toimivassa pseudokoodissa on jotain samantapaista ideaa.

Ehkä sitä tehtävää voisi helpottaa niin, että aluksi kokeilee luoda listan kaikista mahdollisista listan alkioiden yhdistelmistä ja sen jälkeen alkaa karsia niitä vaihtoehtoja. Siinä ei kyllä voi käyttää tavallista silmukkaa, koska se vaatisi sisäkkäisiä silmukoita niin monta kuin loppuvastauksessa on lukuja.

Koodia: [Valitse]

def kaikkimahdollisetkolmenyhdistelmät(LISTA):
    for merkki in LISTA:
        for merkki2 in LISTA:
            for merkki3 in LISTA:
                print([merkki, merkki2, merkki3])
               
kaikkimahdollisetkolmenyhdistelmät("ABCDEFG")

Miten sinä yleistäisit tuon niin, että sisäkkäisten silmukoiden määrän voisi valita?

[Lepotila zZ]

Minäkin ehdin miettiä tätä ennen kun luin edellisessä postauksessa annetun ratkaisun. Tein ensin iteratiivisen version, joka kuitenkin toimi vain annetuilla parametreilla. Tein sitten rekursiivisen version, jonka pitäisi toimia muillakin parametreilla. Asiaa hieman mietittyäni, ja luettuani edellisen postauksen, minusta vaikutti siltä, että iteratiivisenkin version voi toteuttaa siten, että se hyväksyy eri parametreja. Tässä tulos, joka on toki edellä esitettyä rekursiivista ratkaisua rumempi:

Koodia: [Valitse]

lista = ['a','b','c','d','e','f']
max_pituus = 4

def tulosta_kombinaatio(blokatut):
    l = []
    for i in range(len(lista)):
        if i not in blokatut:
            l.append(lista[i])
    print(l)

blokatut = [x for x in range(len(lista)) if x >= max_pituus]

while True:
    tulosta_kombinaatio(blokatut)
    edellinen = len(lista)
    blokatut[-1] -= 1
    for i in range(len(blokatut) - 1, 0, -1):
        if blokatut[i] == blokatut[i-1]:
            blokatut[i] = edellinen - 1
            edellinen = blokatut[i]
            blokatut[i - 1] -= 1
    if blokatut[0] == -1:
        break
(Blokatut tarkoittaa tässä niitä indeksejä, joita vastaavia elementtejä ei sisällytetä kombinaatioon.) Toisin kuin edellisessä postauksessa esitetty ratkaisu, tämä ei kerää listaa kombinaatioista myöhemmin tulostettavaksi, vaan tulostaa jokaisen kombinaation heti. En tiedä, onko tämä rekursiivista ratkaisua nopeampi vai hitaampi.

En mene myöskään vannomaan, että täm on oikein, mutta vaikuttaa siltä minun silmääni, ja vastausten rivimäärät vastaavat käyttäjän UnelmaIkuisestaOnnesta antaman version vastausten rivimääriä. (En jaksa viritellä ohjelmallista tarkistusta.)

[Lepotila zZ]

Tässä vielä rekusiivinen versio, jonka hahmottelin ennen kun luin käyttäjän UnelmaIkuisestaOnnesta antaman ratkaisun. Muokkasin ratkaisuani kuitenkin antamaan vastaavan tulosteen. Oma ratkaisuni tulostaa kombinaatiot suoraan puun lehdissä sen sijaan, että se keräisi niitä listaan, joka tulostetaan myöhemmin. Ehkä tämä versio voi olla jollekin helpompi ymmärtää:

Koodia: [Valitse]

lista = ['a','b','c','d','e','f']
max_pituus = 4

def rekursiivisesti(A, positio):
    if len(A) == max_pituus:
        print(A)
        return
    if positio < len(lista):
        A.append(lista[positio])
        rekursiivisesti(A, positio + 1)
        del A[-1]
        rekursiivisesti(A, positio + 1)

rekursiivisesti([], 0)

[Jere Sumell]

Jokseenkin tuntuu luontevammalta, että sen sijaan, että ohjelman suoritusvaiheessa kone kävisi noita kombinaatioita läpi yrittäen sitten muodostaa sisäisiin taulukoihin niitä yhdistelmiä, vaikuttaa ensipurennalta tuo blokkaamis-idea käytännöllisemmältä, ja resursseja enemmän säästävältä.

Sittenhän siinä käsitin, että poistuu tuo useimpien siäsisten silmukoiden määrittely siihen lähdekoodiin, ja helposti meneekin yli ymmärryksen, jos taulukossa on useampia sisäisiä taulukoita, 2-ulotteinen taulukko nyt niin mene yli hilseen, mutta helposti siinä alkaa aika pian miettimään miten tämä nyt meneekään?

Kuitenkin mielestäni on järkevää, että ohjelmoijalla pysyy se ohjelman se osakokonaisuus, mitä on ohjelmoimassa kuitenkin sillä tavalla mielessä koko ajan ohjelman lähdekoodin luonnin aikana, niin siinä vähentyy todennäköisemmin virheiden mahdollisuudet. Tämä nyt siitä tuntumasta, että jos ohjelma on niin monimutkaisten rakenteiden sisältämä, niin ohjelmoija itsekään ymmärrä sitä tai pysy kärryillä, niin varmasti tulee virheitä ja todennäköisemmin ohjelmaa ei edes pysty ajamaan.

[Jere Sumell]

Katselin hakukoneella Pythonin osalta, mitä löytyy aiheesta niin tuli vastaan itertools - kirjasto, mikä sisältää funktioita luomaan noita iteraatiota hyödyntäviä ulostuloja tehokkaalla toistorakenne -menetelmällä. Jos Pythonilla implementoi oman pseudo-viritelmän, voisiko tuosta olla apua?

https://docs.python.org/3/library/itertools.html

Ainakin tuota kirjastoa hyödyntämällä varmaankin saa tehostettua sitä, että tarvitsee miettiä niitä silmukoiden lukumääriä yms itse sen ihmeemmin?

[Lepotila zZ]

Joo näyttää, että combinations-funktio tuottaa halutun tuloksen:

Koodia: [Valitse]

import itertools

for x in itertools.combinations('abcdef', 4):
    print(x)
(Tulostusmuoto on tässä vähän erilainen, koska tulos ei koostu tulostettavista listoista, vaan rivit ovat tupleja.

[Jere Sumell]

Tässä nyt valmis koodi tämän aloittamani säikeen iteroitavalla joukolla noita alkioita, ja jos nyt sama esimerkin vuoksi sitten 4:n sarjoja.

Koodia: [Valitse]

#combinations() - valmis lähdekoodi Pythonilla
import itertools
alkiojoukko = [1,2,3,4,5,6]
combs = tuple(itertools.combinations(alkiojoukko, 4))
print(combs)

Sitten ulostulo-tuloste näyttää ihan siltä, mitä alunperin hainkin, niinkuin ohjelman pitääkin näyttää, kun se toimii oikein.

Koodia: [Valitse]

((1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 3, 6), (1, 2, 4, 5), (1, 2, 4, 6), (1, 2, 5, 6), (1, 3, 4, 5), (1, 3, 4, 6), (1, 3, 5, 6), (1, 4, 5, 6), (2, 3, 4, 5), (2, 3, 4, 6), (2, 3, 5, 6), (2, 4, 5, 6), (3, 4, 5, 6))
Jos aika tulee sitten pitkäksi koneella ensi yönä, voisi alkaa tuota combinations -funktiota kääntämään pseudo-kielelle omaksi ajan kuluksi, mitä tuossa dokumentaatiossa aika kattavasti esitetty sekin.

[Jere Sumell]

Määrittelin tuon lisäyksen RATKAISTU tähän säikeen avaukseeni, mitä tuo Pythonin combinations-metodi nyt itselleni riittää, että sain alkuperäisen ongelmani ratkaistua käytännössä.

Pseudo-koodin voi sitten kääntää itse tekstiedistoriin omaksi iloksi tuosta combinations-funktion lähdekoodin määrittelystä.