Blanda virtuella kort

Hej!

Lite halvt en fråga, lite halvt en utmaning...

Att sortera finns det otaliga algoritmer till, men hur är det med det omvända, tag t.ex. att blanda en kortlek.

Att göra detta är enkelt, den mest naiva approachen måste väl ändå vara att för varje element i arrayen (eller lista eller vad ni nu vill) som skall blandas, slumpa ett tal mellan 1 och antal element i arrayen, tolka det som ett index i en ny array och kolla om där finns ett värde. Om inte, "flytta" element från listan som skall blandas till nya arrayen, om det redan finns slumpa nytt tal tills ledig plats hittas.

Problemet med den implementationen är att den är teoretiskt sett väldigt ineffektiv. I slutet kommer de flesta elementen vara insorterade så antalet lediga platser kommer bli få.

Är ni med? Så, har ni några smarta algoritmer/datastrukturer för att blanda en array, som är effektiva? Ni behöver inte använda en array och ni behöver inte ge kodexempel. Gör som ni vill bara man förstår vad ni menar...

jonasc: raden "random.shuffle(self.deck)" gör väl jobbet, eller missförtår jag?

vb: mm, det är en tanke, men längden av en lista med längd n är vanligtvis linjär, kanske det går att optimera ännu mera? Visserligen minskar längden av listan hela tiden...

Den missade jag helt! Tackar!

När jag läser den på det viset förstår jag vb's förslag lite bättre och det är skillnad på att förutsätta något och utföra något. Fel av mig.

Tip top!