C# Unieke array van 10 getallen

dinsdag 9 september 2008 11:13

Ik heb geen compiler bij de hand maar de volgende code doet wat je wilt:

C#:

// Levert een willekeurige permutatie van [1..count] op
public char[] YieldRandomPermutation(char from, char to) {
    List<char> values = new List<char>();
    for(char c=from; c<=to; c++) {
        values.Add(c);
    }
    return YieldRandomPermutation<char>(values); // <char> is overbodig in C# 3.0
}

// Levert een willekeurige permutatie van de opgegeven set op
public T[] YieldRandomPermutation<T>(List<T> values) {
    LinkedList<T> result = new LinkedList<T>();
    Random random = new Random();
    while(values.Count > 0) {
        int index = random.Next(values.Count);
        result.Add(values[index]);
        values.RemoveAt(index);
    }
    return result.ToArray();
}

Edit: Overigens past de tweede methode wel de List<T> die je erin gooit aan. Als je dat niet wilt, moet je een dus kopie aanleveren.
Edit2: Het ging op 'A'...'J'. en niet '1..10'

[ Voor 13% gewijzigd door BramFokke op 09-09-2008 11:25 ]

Acties:

NMe

Quia Ego Sic Dico.

Verwijderd schreef op dinsdag 09 september 2008 @ 09:54:
Ik heb een goed Random voorbeeld gevonden waar ik wel wat mee kan!
Nu worden mij steeds verschillende array's gegeven die ik verder kan gaan gebruiken. thnx!

Begrijp je nu na dit topic ook waarom je eerdere oplossing slecht was? En begrijp je het voorbeeld dat je nu implementeert ook goed genoeg om in detail te kunnen zeggen wat het doet? Want zolang dat niet zo is zal je code waarschijnlijk altijd blijven bestaan uit een raamwerk van goeie bedoelingen, bij elkaar gehouden met ducttape-oplossingen.

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.

dinsdag 9 september 2008 12:33

Acties:

Soultaker

jeanj schreef op dinsdag 09 september 2008 @ 10:37:
gewoon een array vullen met 0..9 en dan x aantal keer 2 random nummers 0..9 genereren en deze swappen...., neem x = 1000 en dat is wel voldoende

Dit is al heel vaak gezegd, maar voor de volledigheid: dit levert geen uniform gedistribueerdere resultaten op. (Bewijs: er zijn precies 10! verschillende uitkomsten, maar er zijn 10^2x mogelijke en even waarschijnlijke executies van het algoritme; aangezien 10^2x != 0 mod 10! (voor welke x dan ook) is niet elke uitkomst even waarschijnlijk).

Een goede manier om een shuffle te implementeren is de Knuth shuffle, of als je wat simpelers wil, elk element associeren met een random key (een willekeurig getal uit een voldoende groot bereik) en daarop sorteren. Beide methoden zijn bovendien veel sneller dan de verwisselmethode.

dinsdag 9 september 2008 13:44

Acties:

dinsdag 9 september 2008 14:02

Dit is toch gewoon het koninginneprobleem op een bord van 10x10?

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com

Acties:

Soultaker

Nee, want koninginnen mogen ook niet op dezelfde diagonaal staan.

Je zou het een probleem met tien torens kunnen noemen, maar eigenlijk is het gewoon een permutatie van 10 getallen.

dinsdag 9 september 2008 14:03

Acties:

Verwijderd

Nee.

(edit: zie bovenstaand)

[ Voor 77% gewijzigd door Verwijderd op 09-09-2008 14:04 ]

dinsdag 9 september 2008 21:24

Acties:

dinsdag 9 september 2008 22:23

Soultaker schreef op dinsdag 09 september 2008 @ 14:02:
Nee, want koninginnen mogen ook niet op dezelfde diagonaal staan.
Je zou het een probleem met tien torens kunnen noemen, maar eigenlijk is het gewoon een permutatie van 10 getallen.

Diagonalen... was ik even vergeten idd.

Maar het idee is volgens mij hetzelfde, althans hoe je het oplost. de constraints zijn alleen soepeler (dus idd torens), maar verder heb je per kolom (== index) een toren op een rij (is value) staan. Althans, als je wilt berekenen of een permutatie idd een permutatie is, dan is dat volgens mij een manier om het te doen.

Maar een shuffle van 0-9 is idd optimaler.

[ Voor 3% gewijzigd door EfBe op 09-09-2008 21:24 ]

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com

Acties:

pedorus

BramFokke schreef op dinsdag 09 september 2008 @ 10:52:
Ik heb geen compiler bij de hand maar de volgende code doet wat je wilt:

Ik zou het toch korter aanpakken:

C#:

1	int waarden[]=Enumerable.Range(0,10).OrderBy(x=>random.Next()).ToArray();

(Ok, dit is O(n log n) ipv O(n) van een Knuth Shuffle, maar zolang n binnen de perken blijft is dat niet echt boeiend)

Vitamine D tekorten in Nederland | Dodelijk coronaforum gesloten

woensdag 10 september 2008 10:31

Acties:

riezebosch

Verwijderd schreef op dinsdag 09 september 2008 @ 09:54:
Ik heb een goed Random voorbeeld gevonden waar ik wel wat mee kan!
Nu worden mij steeds verschillende array's gegeven die ik verder kan gaan gebruiken. thnx!

De vraag is of je er in je oplossing ook voor gezorgd hebt dat er geen dubbelen in voorkomen, want dat kan natuurlijk op het eerste gezicht wel zo lijken als je met random aan de gang gaat. Vandaar ook dat hierboven telkens shufflen geadviseerd wordt als deeloplossing.

[ Voor 7% gewijzigd door riezebosch op 10-09-2008 10:31 ]

Canon EOS 400D + 18-55mm F3.5-5.6 + 50mm F1.8 II + 24-105 F4L + 430EX Speedlite + Crumpler Pretty Boy Back Pack

woensdag 10 september 2008 11:04

Acties:

woensdag 10 september 2008 11:17

pedorus schreef op dinsdag 09 september 2008 @ 22:23:
[...]

Ik zou het toch korter aanpakken:
C#:
1
int waarden[]=Enumerable.Range(0,10).OrderBy(x=>random.Next()).ToArray();
(Ok, dit is O(n log n) ipv O(n) van een Knuth Shuffle, maar zolang n binnen de perken blijft is dat niet echt boeiend)

Dat is inderdaad een elegante oplossing. Maar deze oplossing gaat er wel van uit dat per 'x' random.Next() maar één keer wordt aangeroepen. Als dat niet zo is, dan varieert de key tijdens de sorteerprocedure en krijg je een InvalidOperationException. Ik denk niet dat .NET de key opslaat, want daarvoor is een Dictionary nodig. In dit specifieke geval zou een array volstaan, maar als de range anders is of het om OrderBy<Control> gaat, dan kan dat niet. En die lookup zou O(log n) zijn, waardoor het sorteeralgoritme niet meer O(n log n) is maar O(n log2 n). Maar zeker weet ik het niet, dus dat ga ik zo even proberen.

Edit: Ik heb het even geprobeerd en .NET slaat de keys inderdaad op. Dat betekent dat je bovenstaande code dus prima werkt (en nog eens lekker elegant is!), maar ook dat IEnumerable<T>.OrderBy() O(n log2 n) is. Of mis ik hier iets?

[ Voor 10% gewijzigd door BramFokke op 10-09-2008 11:18 ]

Acties:

BtM909

Watch out Guys...

Verwijderd schreef op dinsdag 09 september 2008 @ 09:54:
Ik heb een goed Random voorbeeld gevonden waar ik wel wat mee kan!
Nu worden mij steeds verschillende array's gegeven die ik verder kan gaan gebruiken. thnx!

In plaats van alleen maar vragen naar oplossingen voor jouw problemen, post hier eens wat voor oplossing je hebt gevonden... Wie weet help je eens een ander

Ace of Base vs Charli XCX - All That She Boom Claps (RMT) | Clean Bandit vs Galantis - I'd Rather Be You (RMT)
You've moved up on my notch-list. You have 1 notch
I have a black belt in Kung Flu.

woensdag 10 september 2008 11:20

Acties:

Teunis

Er zijn al genoeg voorbeelden met randoms gegeven
Tenzijn volgende code echt voor duizenden wil gaan gebruiken,
zou ik zelf eerder voor volgende oplossing kiezen

code:

for (int a = 0; a < 10; a++)
{
    for (int b = 0; b < 10; b++)
    {
        if (b == a) continue;
        for (int c = 0; c < 10; c++)
        {
            if (c == a) continue;
            if (c == b) continue;
            for (int d = 0; d < 10; d++)
            {
                if (d == a) continue;
                if (d == b) continue;
                if (d == c) continue;
                for (int e = 0; e < 10; e++)
                {
                    if (e == a) continue;
                    if (e == b) continue;
                    if (e == c) continue;
                    if (e == d) continue;
                    for (int f = 0; f < 10; f++)
                    {
                        if (f == a) continue;
                        if (f == b) continue;
                        if (f == c) continue;
                        if (f == d) continue;
                        if (f == e) continue;
                        for (int g = 0; g < 10; g++)
                        {
                            if (g == a) continue;
                            if (g == b) continue;
                            if (g == c) continue;
                            if (g == d) continue;
                            if (g == e) continue;
                            if (g == f) continue;
                            for (int h = 0; h < 10; h++)
                            {
                                if (h == a) continue;
                                if (h == b) continue;
                                if (h == c) continue;
                                if (h == d) continue;
                                if (h == e) continue;
                                if (h == f) continue;
                                if (h == g) continue;
                                for (int j = 0; j < 10; j++)
                                {
                                    if (j == a) continue;
                                    if (j == b) continue;
                                    if (j == c) continue;
                                    if (j == d) continue;
                                    if (j == e) continue;
                                    if (j == f) continue;
                                    if (j == g) continue;
                                    if (j == h) continue;
                                    for (int k = 0; k < 10; k++)
                                    {
                                        if (k == a) continue;
                                        if (k == b) continue;
                                        if (k == c) continue;
                                        if (k == d) continue;
                                        if (k == e) continue;
                                        if (k == f) continue;
                                        if (k == g) continue;
                                        if (k == h) continue;
                                        if (k == j) continue;

                                        string st = string.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}", a, b, c, d, e, f, g, h, j,k);
                                        Console.WriteLine(st);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

Voordeel je controleert duplicaten tijdens het genereren.
(als B het zelfde getal heeft als A skip de rest, etc);

klein is de code niet, en waarschijnlijk kan het veel neter geprogrameered worden maar gaat even om het idee

Please nerf Rock, Paper is fine. Sincerely yours, Scissor.
GW2:Teunis.6427

woensdag 10 september 2008 11:24

Acties:

woensdag 10 september 2008 11:29

MikroTik nerd

offtopic:
Ben je toevallig met Sudoku's bezig ?

Eerst het probleem, dan de oplossing

Acties:

Jaap-Jan

Als je wilt checken op duplicaten, doe dan gewoon een sort en kijk de array door.

Als je wilt shufflen, pak dan het Knuth algoritme. Ik ben niet zo'n ster in formele notatie, maar ik begrijp wel hoe dat algoritme werkt en dat is vrij simpel. Op de wikipedia pagina die Soultaker noemde, staat zelfs al een implementatie in Java, die vrij simpel te porten is naar C#.

| Last.fm | "Mr Bent liked counting. You could trust numbers, except perhaps for pi, but he was working on that in his spare time and it was bound to give in sooner or later." -Terry Pratchett

woensdag 10 september 2008 11:30

Acties:

woensdag 10 september 2008 11:40

@Teunis: Die code levert ALLE permutaties op. En dat zijn er nogal wat. 10! ofwel 3.6 miljoen.

Acties:

Teunis

@BramFokke, weet ik maar wat ik begreip uit de TS verhaal is dit wat hij wel zoekt.
tenzij het idd een soduko achtige iets is.
en dus als 3 op positie 0 bevind, voor 1 van de resultaten dan niet voor de rest van de sequence een 3 op positie 0
dan wordt heel ander verhaal.

Please nerf Rock, Paper is fine. Sincerely yours, Scissor.
GW2:Teunis.6427

woensdag 10 september 2008 11:42

Acties:

pedorus

BramFokke schreef op woensdag 10 september 2008 @ 11:04:
Edit: Ik heb het even geprobeerd en .NET slaat de keys inderdaad op. Dat betekent dat je bovenstaande code dus prima werkt (en nog eens lekker elegant is!), maar ook dat IEnumerable<T>.OrderBy() O(n log2 n) is. Of mis ik hier iets?

Hoe het precies werkt weet ik ook niet, maar ik vermoed dat ze bijvoorbeeld binary tree sort gebruiken. Je hebt dan toch al een hulpobject per bronobject nodig, waar je ook de waarde in op kan slaan. Het maken van die hulpobjecten is O(n).

Vitamine D tekorten in Nederland | Dodelijk coronaforum gesloten

woensdag 10 september 2008 11:49

Acties:

woensdag 10 september 2008 13:11

pedorus schreef op woensdag 10 september 2008 @ 11:42:
[...]

Hoe het precies werkt weet ik ook niet, maar ik vermoed dat ze bijvoorbeeld binary tree sort gebruiken. Je hebt dan toch al een hulpobject per bronobject nodig, waar je ook de waarde in op kan slaan. Het maken van die hulpobjecten is O(n).

Bedankt voor de info. Mijn kennis van sorteeralgoritmen is duidelijk nogal roestig. Schande!

.

@Teunis:
Hier overigens een stukje code waarmee je alle permutaties van een willekeurige IEnumerable<T> kan listen:

C#:

public static IEnumerable<T[]> AllPermutations<T>(this IEnumerable<T> items) {
    T[] source = items.ToArray();
    T[] result = new T[source.Length];
    bool[] visited = new bool[source.Length];
    foreach(T[] t in AllPermutations(source, result, visited, 0)) {
        yield return t;
    }
}

private static IEnumerable<T[]> AllPermutations<T>(T[] source, T[] result, bool[] visited, int index) {
    if(index == source.Length) {
        yield return result;
    } else {
        for(int i = 0; i < source.Length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result[index] = source[i];
                foreach(T[] t in AllPermutations(source, result, visited, index + 1)) {
                    yield return t;
                }
                visited[i] = false;
            }
        }
    }
}

Acties:

woensdag 10 september 2008 13:17

Moderator Devschuur®

Demotivational Speaker

Soultaker schreef op dinsdag 09 september 2008 @ 12:33:
Een goede manier om een shuffle te implementeren is de Knuth shuffle

Mijn god, is daar een wetenschappelijk gepubliceerd algoritme voor?

[ Voor 4% gewijzigd door .oisyn op 10-09-2008 13:11 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Acties:

woensdag 10 september 2008 13:55

.oisyn schreef op woensdag 10 september 2008 @ 13:11:
[...]

Mijn god, is daar een wetenschappelijk gepubliceerd algoritme voor?

Ik baal er soms nog van dat ik niet een jaar of dertig ouder was, zodat ik mijn naam had kunnen geven aan iets triviaals als het Floyd-Warshall algoritme

Acties:

woensdag 10 september 2008 14:06

Moderator Devschuur®

Demotivational Speaker

Maar we moeten er natuurlijk wel een beetje rekening mee houden dat wij ermee zijn opgegroeid (ik zie trouwens dat we uit hetzelfde bouwjaar zijn

), terwijl het voor hen nog allemaal nieuw was

.

offtopic:
Desalniettemin, ik was 13 toen ik de HespKnuth Shuffle bedacht, in QuickBasic om een random permutatie te krijgen van woordjes in mijn woordjes-overhoor-programma (overhoor.bas). En het is zo logisch: je hebt een zak knikkers, en je trekt er iedere keer een willekeurige uit

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Acties:

woensdag 10 september 2008 14:17

.oisyn schreef op woensdag 10 september 2008 @ 13:55:
Maar we moeten er natuurlijk wel een beetje rekening mee houden dat wij ermee zijn opgegroeid (ik zie trouwens dat we uit hetzelfde bouwjaar zijn ), terwijl het voor hen nog allemaal nieuw was .

offtopic:
Desalniettemin, ik was 13 toen ik de HespKnuth Shuffle bedacht, in QuickBasic om een random permutatie te krijgen van woordjes in mijn woordjes-overhoor-programma (overhoor.bas). En het is zo logisch: je hebt een zak knikkers, en je trekt er iedere keer een willekeurige uit

Absoluut waar. En sommige pioniers hebben echt briljante dingen gedaan, zoals Turing en van Neumann $_/-\o_$ . Maar sommige algoritmen zijn zo triviaal dat ze eigenlijk de naam algoritme niet verdienen en ik reken het Floyd-Warshall (edited) algoritme (lees: enkele geneste loops) daar even onder

. Maar goed, 'onze tijd' heeft ook weer voordelen. Zo hebben wij de tools tot onze beschikking waardoor je in een paar middagen een hele applicatie in elkaar schroeft en dat had je toen weer niet.

EDIT: Oeps, ik had het natuurlijk over Floyd-Warshall en niet over Bellman-Floyd.

[ Voor 4% gewijzigd door BramFokke op 10-09-2008 14:25 ]

Acties:

Soultaker

Bellman-Floyd? Heb je het nu over Floyd-Warshall of Bellman-Ford? Zijn niet dezelfde algoritmen!

Verder vind ik dat soort algoritmen toch wel van enig inzicht getuigen. Natuurlijk, Floyd-Warshall zijn drie geneste lusjes, en dat ziet er triviaal uit, maar als je na gaat denken waarom het werkt, is het toch wel slim.

Ik vind het sowieso een goed idee om dit soort standaardalgoritmen een naam te geven; dan ligt de naam van iemand die het (voor het eerst) beschrijft voor de hand. Knuth schrijft studieboeken voor informatici, dus nogal logisch dat hij een hoop standaardalgoritmen beschrijft, en mensen dan de term Knuth shuffle gaan gebruiken om naar het door hem beschreven algoritme te verwijzen. Dat betekent niet dat er altijd een e=mc²-achtige openbaring aan ten grondslag ligt.

Verder zijn er natuurlijk 'tig slimme algoritmen die geen naam hebben, maar die dat pas krijgen als ze algemeen toepasbaar blijken te zijn. Dus doe je best, en verzin wat nieuwe technieken, publiceer ze, en wie weet ben je over vijftig jaar ook beroemd^*.

_{* = bekend bij een kleine groep nerds met een informatica-achtergrond}

woensdag 10 september 2008 14:22

Acties:

woensdag 10 september 2008 14:23

MikroTik nerd

Als ik een voorstel mag doen met pseudo code:

code:

A:
Verzameling {1,...,9}
Pak de eerste uit de verzameling
Maak de verzameling kleiner

B:
Verzameling {2,...,9}
Pak de eerste uit de verzameling
Maak de verzmaling kleiner

Enz.

Hierin zie je een bepaalde recursiviteit terug komen en je beperkt het aantal vergelijkingen dat je moet doen (want die zijn relatief duur en niet nodig).

Eerst het probleem, dan de oplossing

Acties:

woensdag 10 september 2008 14:29

Floyd Warshall is echt niet 'triviaal'. Het gaat er om dat algorithmes die aangetoond correct en een bewezen orde hebben gepubliceerd worden zodat ieder ander zn eigen naive troep vervangt door deze bewezen algorithmes.

Ik bedoel, hoeveel depth-first-seach based algo's zijn er niet op graphs? Allemaal te simpel voor woorden? Ik denk het niet, het punt is juist dat ze bewezen correct zijn, of ze simpel zijn of niet dat doet niet terzake (shellsort oid is ook maar een paar regels). Bewezen correcte algorithmes hebben het voordeel dat je als developer alleen nog je implementatie van het algorithme hoeft te controlleren (en dat kan zonder code te runnen) en niet ook nog eens het algorithme zelf te testen (want tests doen nl. beide).

Dus ik snap oisyn's reactie in het geheel niet.

.oisyn schreef op woensdag 10 september 2008 @ 13:55:

offtopic:
Desalniettemin, ik was 13 toen ik de HespKnuth Shuffle bedacht, in QuickBasic om een random permutatie te krijgen van woordjes in mijn woordjes-overhoor-programma (overhoor.bas). En het is zo logisch: je hebt een zak knikkers, en je trekt er iedere keer een willekeurige uit

Tuurlijk

Mijn virtual memory manager voor mn msx2 was ook superuniek dacht ik op mn 16e maar dat bleek niet het geval toen ik het college OS-internals volgde (duh). Dat neemt niet weg dat als iemand daar tijd in steekt en gaat bewijzen dat bepaalde software correct is, het wel degelijk wetenschap is en een publicatie waard: immers: omdat het bewijs er ligt kan iedereen vanaf dat moment het klakkeloos gebruiken binnen de grensen van het bewijs. Dat jij denkt dat zo'n algorithmetje 'natuurlijk altijd werkt' is niet per se waar: zonder bewijs red je het niet. Iedere programmeur heeft op een gegeven moment een algorithme bedacht waarvan z/hij heilig overtuigd was dat het feilloos werkte, maar dat bleek achteraf toch niet het geval, ookal was het nog zo simpel. Standaardvoorbeeld: element uit doubly linked list verwijderen.

[ Voor 44% gewijzigd door EfBe op 10-09-2008 14:28 ]

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com

Acties:

woensdag 10 september 2008 14:47

@Soultaker:
He bah, niets zo irritant als valide argumenten tegen een overtrokken reactie

Acties:

woensdag 10 september 2008 18:29

Moderator Devschuur®

Demotivational Speaker

EfBe schreef op woensdag 10 september 2008 @ 14:23:
Dus ik snap oisyn's reactie in het geheel niet.

Ik had het over Knuth, niet over Floyd-Warshall

Standaardvoorbeeld: element uit doubly linked list verwijderen

Heb je het dan over het vergeten je first en last pointers te updaten als je het eerste en/of het laatste element verwijderd?

[ Voor 32% gewijzigd door .oisyn op 10-09-2008 14:49 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Acties:

Grijze Vos

lier schreef op woensdag 10 september 2008 @ 14:22:
Hierin zie je een bepaalde recursiviteit terug komen en je beperkt het aantal vergelijkingen dat je moet doen (want die zijn relatief duur en niet nodig).

Vergelijkingen relatief duur, en dan kom je met een term als recursie, i.e. function calls, terwijl dit gewoon heel simpel iteratief is aan te pakken. Daarnaast zit je arrays/lists te editen, wat afhankelijk van de implementatie ook nogal duur kan zijn.

Ik zou het gewoon houden bij het eerder geposte simpele algoritme.

Op zoek naar een nieuwe collega, .NET webdev, voornamelijk productontwikkeling. DM voor meer info

donderdag 11 september 2008 09:02

Acties:

donderdag 11 september 2008 09:06

.oisyn schreef op woensdag 10 september 2008 @ 14:47:
[...]

Ik had het over Knuth, niet over Floyd-Warshall

Ah. Maar dan nog..

Heb je het dan over het vergeten je first en last pointers te updaten als je het eerste en/of het laatste element verwijderd?

Nee, de fout dat je in het element dat je eruit haalt (en bv wel wil bewaren) de prev/next op null zet maar dan niet meer de twee delen van de list aan elkaar kan knopen.

Creator of: LLBLGen Pro | Camera mods for games
Photography portfolio: https://fransbouma.com

Acties:

donderdag 11 september 2008 21:03

MikroTik nerd

Grijze Vos schreef op woensdag 10 september 2008 @ 18:29:
Vergelijkingen relatief duur, en dan kom je met een term als recursie, i.e. function calls, terwijl dit gewoon heel simpel iteratief is aan te pakken. Daarnaast zit je arrays/lists te editen, wat afhankelijk van de implementatie ook nogal duur kan zijn.

Ik zou het gewoon houden bij het eerder geposte simpele algoritme.

Je hebt het over een list van 10 items waar je elke keer een waarde uit haalt (en vervolgens weer toe voegt). Daardoor kan je alle vergelijkingen over slaan (en ja, deze zijn echt duur en overbodig !).

Leg trouwens nog even de relatie tussen recursie en vergelijkingen uit, die ontgaat mij volledig. En waarom is mijn (pseudo) oplossing niet iteratief ?

Oh ja...been there, done that.

Eerst het probleem, dan de oplossing

Acties:

Jaap-Jan

lier schreef op donderdag 11 september 2008 @ 09:06:
[...]

Je hebt het over een list van 10 items waar je elke keer een waarde uit haalt (en vervolgens weer toe voegt). Daardoor kan je alle vergelijkingen over slaan (en ja, deze zijn echt duur en overbodig !).

Leg trouwens nog even de relatie tussen recursie en vergelijkingen uit, die ontgaat mij volledig. En waarom is mijn (pseudo) oplossing niet iteratief ?

Oh ja...been there, done that.

Hoeveel vergelijkingen zie je in dit stuk code?

Java:

    public static void shuffle (int[] array) 
    {
        Random rng = new Random();   // i.e., java.util.Random.
        int n = array.length;        // The number of items left to shuffle (loop invariant).
        while (n > 1) 
        {
            int k = rng.nextInt(n);  // 0 <= k < n.
            n--;                     // n is now the last pertinent index;
            int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
            array[n] = array[k];
            array[k] = temp;
        }
    }

Ik tel er maar één die elke iteratie wordt uitgevoerd. 10 vergelijkingen lijkt mij een stuk goedkoper dan 10 functieaanroepen.

| Last.fm | "Mr Bent liked counting. You could trust numbers, except perhaps for pi, but he was working on that in his spare time and it was bound to give in sooner or later." -Terry Pratchett

donderdag 11 september 2008 21:38

Acties:

writser

Of je googlet op "java shuffle array" en klikt op de eerste hit:

Java:

1	Collections.shuffle(Arrays.asList(waarden));

Leer je misschien wel wat minder van.

Onvoorstelbaar!

vrijdag 12 september 2008 08:51

Acties:

vrijdag 12 september 2008 13:14

MikroTik nerd

Jaap-Jan schreef op donderdag 11 september 2008 @ 21:03:
Ik tel er maar één die elke iteratie wordt uitgevoerd. 10 vergelijkingen lijkt mij een stuk goedkoper dan 10 functieaanroepen.

Aha...ik reageerde eigenlijk meer op Teunis voorstel...

(wellicht daarom de verwarring)

Eerst het probleem, dan de oplossing

Acties: