Array-Inhalt auf Einzigartigkeit überprüfen

[huha]

Morgen!

Da ich nun endlich mal etwas in Sachen KI machen will bzw. mir einfach langweilig ist, dachte ich, daß ich doch mal das Traveling Salesman Problem in VB angehen kann.
Leider habe ich ein Problem, vielleicht weiß ja jemand eine ordentliche Lösung:

Ich habe ein Array. In diesem Array stehen nun zufällig ausgewählt die Stadtnummern drin, also zum Beispiel 4, 3, 1, 2.

Leider liefert der Zufallsalgorithmus natürlich auch mehrmals die selben Werte, also kann es auch sein, daß 4,1,4,2 drinsteht.
Letztere Sitation will ich möglichst vermeiden, da das unnötige Verschwendung von Rechenkapazität ist und wer VB kennt, weiß, daß sich das sofort auf die Geschwindigkeit auswirkt ;)
Also, kennt jemand einen Algorithmus oder einen Codeschnipsel, mit dem ich verhindern kann, daß die selben Zahlen in dem Array mehrmals vorkommen?

Danke!

-huha

[liquid]

Könntest das ja so machen.

Ein Array mit X Elementen nehmen (X stellt die Gesamtzahl der Städte dar - also bei 10 Städten wäre X = 10) und mit 0,1,2,3,4,5,.... füllen.

Dann eine Zufallszahl zwischen 0 und X-1 erzeugen.
Mit array[die_eben_erzeugte_zahl] die dort gespeicherte Zahl holen und in ein anderes Array speichern. Die Position im ersten Array dann auf -1 setzen.
Und halt am Anfang (wenn man dort zugreift) gucken, ob der Wert kleiner Null ist (also schon geholt wurde). Wenn der schon geholt wurde neue Zufallszahl erzeugen und neu versuchen. Ist natürlich nicht so schön (performancemäßig), weil man unter Umständen mehrmals hintereinander Zufallszahlen erzeugen muss.

Vielleicht kannste das auch so machen, dass du quasi einen Zahlenpool erstellst indem jede Zahl nur einmal vorkommt und dann per Zufall reingrabscht und dir eine rausholst. Wie das implementierungsbedingt zu machen wäre..... *boah bin ich müde* KA, musste halt mal selber gucken ;)

cya
liquid

[bulla]

hm
1.ein array bilden, evtl., bei sehr grossen zahlenmengen, als baum implementieren
2.random-zahl wird erzeugt
3.random-zahl in array auf existenz überprüfen, wenn false ->einfügen, andernfalls nächste randomzahl


falls du ein array auf "randomisiertheit" überprüfen willst:

temp-array bilden
zahlen aus dem original-array nach und nach ins temp-array per einfügungs-verfahren kopieren

evtl. vorteil: du hast es gleichzeitig sortiert, könnte effizienter sein

[ethrandil]

Thehe, machs doch so: Du willst Zufallszahlen von
0 - 1000
Dann machst du erstmal ein Array mit der länge 1001 durchnummeriert von vorne bis hinten. Dann machst du jeweils 2 Zufallszahlen von 0 - 1001 und vertauscht die entsprechenden Array-Einträge :)

Mal ne andere Methode, weiß nicht ob die so performant ist, nur wenn eh alle was anderes machen :naughty:
EDIT: Wenn du im endeffekt nur 20 Zahlen von 1001 haben willst, dann nimmst du halt nur die ersten 20 Im resultierenden Array.

[ethrandil]

Oder ne ähnliche Methode:
Du hast ja ne begrenzte anzahl an Ländern.
Nehmen wir mal ... X :)
Dann machst du ja zufallszahlen von 0 - X.
Dann legst du dir einfach ein Array mit der Länge X an, und wenn die Zufallszahl Z fällt, dann guckst du, ob an Stelle Z in Array false ist. Wenn nicht nimmst du die gefallene Zufallszahl und setzt das Array an Z = true. Wenn dort schon true ist, dann ziehst du solange ne neue Zahl, bis das entsprechende Feld false ist.
klar?

Dürfte Performanter sein als mein erster Vorschlag.
Beispielcode (ohne gewähr):

int städtearray[städteanzahl];
bool zufallsTemp[städteanzahl];
for(int i = 0; i < städteanzahl; ++i){
int zufallszahl = (int)(rand()*städteanzahl);
while(zufallsTemp[zufallszahl] == true)
zufallszahl = (int)(rand()*städteanzahl);
zufallsTemp[zufallszahl] = true;
städtearray[i] = zufallszahl;
}

Schick, nicht? *proudly*

Vorher musst du natürlich noch das bool-array voll mit falses packen :)

[DocEW]

Hab hier kein VB, daher "nur" Java (kannste ja sicher übertragen):


int size = 4;
int[] staedte = new int[size];
int[][] pool = new int[size][3];
int wahl;

// initialisieren: [0]=wert, [1]=vorgänger, [2]=nachfolger
for ( int i = 0; i < size; i++ ) {
pool[i][0] = i;
pool[i][1] = i-1;
pool[i][2] = i+1;
}

// spezialbehandlung: voränger des 0. Elements ist das letzte...
pool[0][1]=size-1;
// ...und nachfolger des letzten ist das 0.
pool[size-1][2]=0;

// und los...
for ( int aktStadt = 0; aktStadt < size; aktStadt++ ) {
wahl = (int) (size * Math.random());

// evtl. wahl korrigieren, fals schon vorher genommen
while ( pool[wahl][0] == -1 ) {
wahl = pool[wahl][2];
}

// wahl als vergeben markieren
pool[wahl][0] = -1;

// vorgänger von anpassen (genauer: nachfolger d. Vorgängers
pool[ pool[wahl][1]][2] = pool[wahl][2];

// und schließlich: wahl nehmen! :-)
staedte[aktStadt] = wahl;
}

for ( int i = 0; i < size; i++ ) {
System.out.print( staedte[i] + " " );
}

[DocEW]

Ach ja, für sowas sind immer funktionale Sprachen geil.
Hier mal ein Beispiel der total bekannten ;) Sprach Haskell:


perm [] = [[]]
perm li = [ (li!!x) : rest
| x<- [0..(length li-1)] ,
rest <- perm ((take x li) ++ (drop (x+1) li))]


Dieser riesige Codehaufen liefert alle Permutationen.
Eine Eingabe von

perm [1..3]

liefert z.B.

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

=)