Just nu i M3-nätverket
Jump to content

Lista alla möjliga kombinationer!


Peter Lindvall

Recommended Posts

Peter Lindvall

Hej!

 

Hur gör man för att lista alla möjliga kombinationer av x antal tecken. Varje tecken får endast förekomma en gång. Programmet ska skrivas i C++.

 

Ett exempel: ABC, BAC, BCA, CBA, CAB, ACB.

 

Tacksam för tips om hur man ska tänka när man utformar algoritmen.

 

Link to comment
Share on other sites

-Patrik Johansson-

Känner du till binära träd?

Tänk dig då att i första ledet finns x löv som är de enskilda bokstäverna.

Till varje löv sedan så kopplas x nya löv till varje föregångende löv. Sedan håller man på så tills man har fått x led.

Då blir varje led från sista till första löv en kombination av tecken.

 

Nu får du med alla kombinationer så du får sortera ut dem som innehåller löv där minst två av löven är lika.

 

/Neox -(Patrik J)

"Gravitation can not be held responsible for people falling in love"
- citat av Albert Einstein

 

Link to comment
Share on other sites

Peter Lindvall

Jag känner till binära träd, och förstår hur du tänker... det jag hänger upp mig på är att om man sätter in x antal löv under rooten kommer det inte att vara något binärt träd. Har jag tre tecken kommer roten att ha tre noder på första nivån, detsamma gäller alla underliggande nivåer också. Har jag sedan fyra tecken kommer det att bli fyra noder på första nivån osv...

Din idé är som jag förstår det att bibehålla en binär struktur oavsett hur många tecken som finns med i den ursprungliga teckensträngen.

 

Om man däremot sätter in "tomma noder" här och där, kan man tvinga trädet att alltid bibehålla den binära strukturen. Det blir dock lite bökigare, samtidigt som idéen med att trädet är klart när man uppnått ett djup av x nivåer faller.

 

Har jag kanske missförstått dig?

Tack för ett i övrigt bra svar!

 

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.



×
×
  • Create New...