Kaikkien osajoukkojen generointi
Valitse jokainen alkio tai ohita se
Kaikkien osajoukkojen generointi on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Miksi osajoukkoja muodostetaan
Monissa kilpailutehtävissä pyydetään kokeilemaan pienen joukon jokaista osajoukkoa. Rekursion avulla voitte luetella ne kaikki selkeästi ja luotettavasti. 🧩
Valitkaa tai ohittakaa kukin alkio
Perusidea on seuraava: jokaisesta alkiosta tehdään yksi binäärinen valinta — otetaanko alkio mukaan vai jätetäänkö se pois. Jokainen valintojen täydellinen yhdistelmä muodostaa yhden osajoukon.
Kuinka monta osajoukkoa on
Joukossa, jossa on n alkiota, on täsmälleen 2 potenssiin n osajoukkoa, koska jokainen alkio kaksinkertaistaa määrän. Pitäkää siis n pienenä, noin 20:ssä tai sen alle.
Rekursiivinen suunnitelma
Kuljettakaa indeksiä taulukon läpi. Haarautukaa jokaisessa indeksissä kahdesti: kerran ottamalla alkio mukaan ja kerran ohittamalla sen.
Perustapaus
Kun indeksi ohittaa viimeisen alkion, nykyinen polku on yksi valmis osajoukko. Silloin saavutaan perustapaukseen, jossa osajoukko tallennetaan.
Osajoukkojen rekursio koodissa
Tämä rekursiivinen läpikäynti tallentaa osajoukon lopussa ja tutkii sitten jokaisesta indeksistä sekä ohitus- että valintahaaraa.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Tehkää takaisinhaku kumoamalla valinta
Kun lisäätte alkion, poistakaa se rekursion jälkeen, jotta seuraava haara alkaa puhtaasta tilasta. Tämä kumoamisvaihe on takaisinhaun ydin.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()Bittimaskin vaihtoehto
Voitte myös kuvata jokaisen kokonaisluvun 0:sta lukuun 2 potenssiin n − 1 asti yhtenä osajoukkona, jossa jokainen bitti ilmaisee, kuuluuko vastaava alkio mukaan.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Kopioikaa ennen tallentamista
Tallentakaa aina nykyisen listan kopio, ei itse listaa. Muuten myöhemmät muutokset korvaavat kaikki tallentamanne osajoukot. ⚠️
Kombinaatioiden muodostaminen
Kun haluatte osajoukkoja, joiden koko on k, lopettakaa haara, kun valittujen alkioiden määrä saavuttaa k:n. Näin osajoukoista tulee kombinaatioita.
Missä osajoukkoja käytetään
Osajoukkojen luettelointi ratkaisee pieniä reppuongelmia, joukkueiden valintatehtäviä ja kelpoisuustarkistuksia, joissa jokainen mahdollinen valinta on testattava.
Pikatarkistus
Kuinka monta osajoukkoa n alkion joukolla on?
Kertaus: haarautukaa jokaisen alkion kohdalla
Opitte luettelemaan kaikki osajoukot valitsemalla tai ohittamalla jokaisen alkion ja kumoamalla valinnan jokaisen haaran jälkeen. Pitäkää n pienenä, sillä määrä on 2 potenssiin n. 🎯
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Kaikkien osajoukkojen generointi” ilmainen?
Kyllä – oppitunnin ”Kaikkien osajoukkojen generointi” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Kaikkien osajoukkojen generointi”?
Valitse jokainen alkio tai ohita se Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Kaikkien osajoukkojen generointi”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Ajattele rekursiivisesti: kanta ja rekursio
- Kaikkien osajoukkojen generointi
- Permutaatiot ja N-kuningattaren idea
- Karsi selvitäksesi aikarajasta