Fisher-Yates Shuffle - Versionshistorik

Anders: /* C */

2025-04-12T23:58:37Z

← Äldre version		Versionen från 12 april 2025 kl. 23.58
Rad 80:		Rad 80:

	<pre>		<pre>
			#include <stdlib.h>
	#include <stdio.h>		#include <stdio.h>
	~~#include <stdlib.h>~~
	#include <time.h>		#include <time.h>

	~~// Funktion för att byta plats på två element~~
	void ~~swap~~(int a, int b) {		void fyshuffle(int *array, size_t n)
	int temp = *a;		{
	a = b;		size_t i, j; // Elements in array to swap
	*b = temp;		int temp; // Temp store

			// Set the random generator using current time
			srand((unsigned int)time(NULL));
			for (i = n - 1; i > 0; i--) {
			j = rand() % (i + 1);
			int temp = array[j];
			array[j] = array[i];
			array[i] = temp;
			}
	}		}

	~~// Fisher-Yates Shuffle implementation~~
	~~void shuffle(int arr[], int n) {~~
	~~// Initialisera slumptalsgeneratorn med tid som seed~~
	~~srand(time(NULL));~~

	~~// Iterera genom arrayen från sista elementet till det andra~~
	~~for (int i = n - 1; i > 0; i--) {~~
	~~// Generera ett slumpmässigt index mellan 0 och i~~
	~~int j = rand() % (i + 1);~~

	~~// Byt plats på elementen vid position i och j~~
	~~swap(&arr[i], &arr[j]);~~
	}
	}

	~~// Hjälpfunktion för att skriva ut arrayen~~		int main(int argc, char *argv[]) {
	~~void printArray(~~int ~~arr~~[], int n) {		int array[15] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
	for (~~int~~ i = 0; i < n; i++) {		int i;
	printf("%d ", ~~arr~~[i]);
	}		fyshuffle(array, 15);
	printf("\n");
			for (i = 0; i < 15; i++) {
			printf("%d ", array[i]);
			}
			printf("\n");
	}		}

	~~// Exempel på användning~~
	~~int main() {~~
	~~int arr[] = {1, 2, 3, 4, 5};~~
	~~int n = sizeof(arr) / sizeof(arr[0]);~~

	~~printf("Original array: ");~~
	~~printArray(arr, n);~~

	~~shuffle(arr, n);~~

	~~printf("Shuffled array: ");~~
	~~printArray(arr, n);~~

	~~return 0;~~
	}
	</pre>		</pre>

Anders den 22 februari 2025 kl. 01.57

2025-02-22T01:57:45Z

@@ Rad 56: / Rad 56: @@
 För att spara tid kan man byta plats med alla strukna tal och det sista talet i serien och därmed hela tiden ha en sammanhängande ordning med ostrukna tal. Se pseudokoden nedan som gör på det sättet.
 == Pseudokod ==
@@ Rad 75: / Rad 77: @@
   done

Anders den 21 februari 2013 kl. 05.13

2013-02-21T05:13:48Z

← Äldre version		Versionen från 21 februari 2013 kl. 05.13
Rad 82:		Rad 82:

	[[category:Programmering]]		[[category:Programmering]]
	[[category:~~C]]~~		[[category:Algoritmer]]
	~~[[category:Linux~~]]

Anders: /* Funktion */

2013-02-20T21:01:42Z

Funktion

← Äldre version		Versionen från 20 februari 2013 kl. 21.01
Rad 8:		Rad 8:

	== Funktion ==		== Funktion ==
	~~=== Pencil-and-paper method ===~~

	~~As an example, we'll permute the numbers from~~ 1 to 8 ~~using [[#~~Fisher ~~and~~ Yates~~' original method\|Fisher and Yates' original method]]~~. ~~We'll start by writing the numbers out on a piece of scratch paper~~:		Som ett exempel skall vi permutera numren 1 till 8 genom att använda Fisher-Yates metod. Vi skriver talen på en bit papper:

	{\| class="wikitable"		{\| class="wikitable"
Rad 19:		Rad 18:
	\|}		\|}

	~~Now we roll a random number~~ ''k'' ~~from~~ 1 ~~to 8—let's make it 3—and strike out the ''k''th (i.~~e. ~~third) number (3, of course) on the scratch pad and write it down as the result:~~		Nu slumpar vi ett tal ''k'' mellan 1-8, vi kan säga att det blev 3 så vi stryker det 3:e numret från papperet och flyttar det till resultatrutan.

	{\| class="wikitable"		{\| class="wikitable"
Rad 25:		Rad 24:
	! Range !! Roll !! Scratch !! Result		! Range !! Roll !! Scratch !! Result
	\|-		\|-
	\| 1–8 \|\| 3 \|\| 1 2 <s~~><span style="color:gray;"~~>3~~</span>~~</s> 4 5 6 7 8 \|\| 3		\| 1–8 \|\| 3 \|\| 1 2 <s>3</s> 4 5 6 7 8 \|\| 3
	\|}		\|}

	~~Now we pick a second random number~~, ~~this time from~~ 1 to 7~~: it turns out to be~~ 4. ~~Now we strike out the fourth number ''not yet struck'' off the scratch pad—that's number 5—and add it to the result:~~		Vi tar ett nytt slumpmässigt tal, denna gång från 1-7 som matchar de siffror vi ej har strukit. Låt oss säga att det blev 4, så vi stryker det fjärde ej redan strukna numret och flyttar det till resultatrutan.

	{\| class="wikitable"		{\| class="wikitable"
Rad 34:		Rad 33:
	! Range !! Roll !! Scratch !! Result		! Range !! Roll !! Scratch !! Result
	\|-		\|-
	\| 1–7 \|\| 4 \|\| 1 2 <s~~><span style="color:gray;"~~>3<~~/span>~~</s> 4 <s~~><span style="color:gray;"~~>5~~</span>~~</s> 6 7 8 \|\| 3 5		\| 1–7 \|\| 4 \|\| 1 2 <s>3<</s> 4 <s>5</s> 6 7 8 \|\| 3 5
	\|}		\|}

	~~Now we pick the next random number from~~ 1 to 6~~, and then from~~ 1 to 5~~, and so on, always repeating the strike-out process as above:~~		Vi fortsätter på samma vis med ett nytt slumptal, denna gång från 1-6 och sedan 1-5 osv ända tills alla tal är strukna.

	{\| class="wikitable"		{\| class="wikitable"
Rad 43:		Rad 42:
	! Range !! Roll !! Scratch !! Result		! Range !! Roll !! Scratch !! Result
	\|-		\|-
	\| ~~1–6~~ \|\| 5 \|\| 1 2 <s~~><span style="color:gray;"~~>3~~</span>~~</s> 4 <s~~><span style="color:gray;"~~>5~~</span>~~</s> 6 <s~~><span style="color:gray;"~~>7~~</span>~~</s> 8 \|\| 3 5 7		\| 1-6 \|\| 5 \|\| 1 2 <s>3</s> 4 <s>5</s> 6 <s>7</s> 8 \|\| 3 5 7
	\|-		\|-
	\| ~~1–5~~ \|\| 3 \|\| 1 2 <s~~><span style="color:gray;"~~>3~~</span>~~</s> <s~~><span style="color:gray;"~~>4~~</span>~~</s> <s~~><span style="color:gray;"~~>5~~</span>~~</s> 6 <s~~><span style="color:gray;"~~>7~~</span>~~</s> 8 \|\| 3 5 7 4		\| 1-5 \|\| 3 \|\| 1 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> 8 \|\| 3 5 7 4
	\|-		\|-
	\| ~~1–4~~ \|\| 4 \|\| 1 2 <s~~><span style="color:gray;"~~>3~~</span>~~</s> <s~~><span style="color:gray;"~~>4~~</span>~~</s> <s~~><span style="color:gray;"~~>5~~</span>~~</s> 6 <s~~><span style="color:gray;"~~>7~~</span>~~</s> <s~~><span style="color:gray;"~~>8~~</span>~~</s> \|\| 3 5 7 4 8		\| 1-4 \|\| 4 \|\| 1 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> <s>8</s> \|\| 3 5 7 4 8
	\|-		\|-
	\| ~~1–3~~ \|\| 1 \|\| <s~~><span style="color:gray;"~~>1~~</span>~~</s> 2 <s~~><span style="color:gray;"~~>3~~</span>~~</s> <s~~><span style="color:gray;"~~>4~~</span>~~</s> <s~~><span style="color:gray;"~~>5~~</span>~~</s> 6 <s~~><span style="color:gray;"~~>7~~</span>~~</s> <s~~><span style="color:gray;"~~>8~~</span>~~</s> \|\| 3 5 7 4 8 1		\| 1-3 \|\| 1 \|\| <s>1</s> 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> <s>8</s> \|\| 3 5 7 4 8 1
	\|-		\|-
	\| ~~1–2~~ \|\| 2 \|\| <s~~><span style="color:gray;"~~>1~~</span>~~</s> 2 <s~~><span style="color:gray;"~~>3~~</span>~~</s> <s~~><span style="color:gray;"~~>4~~</span>~~</s> <s~~><span style="color:gray;"~~>5~~</span>~~</s> <s~~><span style="color:gray;"~~>6~~</span>~~</s> <s~~><span style="color:gray;"~~>7~~</span>~~</s> <s~~><span style="color:gray;"~~>8~~</span>~~</s> \|\| 3 5 7 4 8 1 6		\| 1-2 \|\| 2 \|\| <s>1</s> 2 <s>3</s> <s>4</s> <s>5</s> <s>6</s> <s>7</s> <s>8</s> \|\| 3 5 7 4 8 1 6
	\|-		\|-
	\|   \|\|   \|\| <s~~><span style="color:gray;"~~>1~~</span>~~</s> <s~~><span style="color:gray;"~~>2~~</span>~~</s> <s~~><span style="color:gray;"~~>3~~</span>~~</s> <s~~><span style="color:gray;"~~>4~~</span>~~</s> <s~~><span style="color:gray;"~~>5~~</span>~~</s> <s~~><span style="color:gray;"~~>6~~</span>~~</s> <s~~><span style="color:gray;"~~>7~~</span>~~</s> <s~~><span style="color:gray;"~~>8~~</span>~~</s> \|\| 3 5 7 4 8 1 6 2		\|   \|\|   \|\| <s>1</s> <s>2</s> <s>3</s> <s>4</s> <s>5</s> <s>6</s> <s>7</s> <s>8</s> \|\| 3 5 7 4 8 1 6 2
	\|}		\|}

			För att spara tid kan man byta plats med alla strukna tal och det sista talet i serien och därmed hela tiden ha en sammanhängande ordning med ostrukna tal. Se pseudokoden nedan som gör på det sättet.

	== Pseudokod ==		== Pseudokod ==

Anders: Created page with "== Bakgrund == Fisher-Yates är en algoritm som används för att slumpmässigt omfördela innehållet i en grupp på ett sätt som fungerar ungefär som när man blandar en ..."

2013-02-20T20:50:10Z

Created page with "== Bakgrund == Fisher-Yates är en algoritm som används för att slumpmässigt omfördela innehållet i en grupp på ett sätt som fungerar ungefär som när man blandar en ..."

Ny sida

== Bakgrund ==

Fisher-Yates är en algoritm som används för att slumpmässigt omfördela innehållet i en grupp på ett sätt som fungerar ungefär som när man blandar en kortlek. Det ger minsta möjliga bias även om pseudoslumptalskällan inte är välfiltrerad och ren.

Sättet som algoritmen arbetar på fungerar ungefär som när man plockar lotter ur en tombola eller blandar en kortlek där man drar en efter en tills det inte längre finns några att dra. Rätt använd är biasen väldigt låg.

Andra namn är också ''the Knuth Shuffle'' efter matematikern Donald E. Knuth som använder denna.

== Funktion ==
=== Pencil-and-paper method ===

As an example, we'll permute the numbers from 1 to 8 using [[#Fisher and Yates' original method|Fisher and Yates' original method]]. We'll start by writing the numbers out on a piece of scratch paper:

{| class="wikitable"
|-
! Range !! Roll !! Scratch !! Result
|-
|   ||   || 1 2 3 4 5 6 7 8 ||  
|}

Now we roll a random number ''k'' from 1 to 8—let's make it 3—and strike out the ''k''th (i.e. third) number (3, of course) on the scratch pad and write it down as the result:

{| class="wikitable"
|-
! Range !! Roll !! Scratch !! Result
|-
| 1–8 || 3 || 1 2 <s>3</s> 4 5 6 7 8 || 3
|}

Now we pick a second random number, this time from 1 to 7: it turns out to be 4. Now we strike out the fourth number ''not yet struck'' off the scratch pad—that's number 5—and add it to the result:

{| class="wikitable"
|-
! Range !! Roll !! Scratch !! Result
|-
| 1–7 || 4 || 1 2 <s>3</s> 4 <s>5</s> 6 7 8 || 3 5
|}

Now we pick the next random number from 1 to 6, and then from 1 to 5, and so on, always repeating the strike-out process as above:

{| class="wikitable"
|-
! Range !! Roll !! Scratch !! Result
|-
| 1–6 || 5 || 1 2 <s>3</s> 4 <s>5</s> 6 <s>7</s> 8 || 3 5 7
|-
| 1–5 || 3 || 1 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> 8 || 3 5 7 4
|-
| 1–4 || 4 || 1 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> <s>8</s> || 3 5 7 4 8
|-
| 1–3 || 1 || <s>1</s> 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> <s>8</s> || 3 5 7 4 8 1
|-
| 1–2 || 2 || <s>1</s> 2 <s>3</s> <s>4</s> <s>5</s> <s>6</s> <s>7</s> <s>8</s> || 3 5 7 4 8 1 6
|-
|   ||   || <s>1</s> <s>2</s> <s>3</s> <s>4</s> <s>5</s> <s>6</s> <s>7</s> <s>8</s> || 3 5 7 4 8 1 6 2
|}

== Pseudokod ==

Randomisera n element på plats i en array

for i from n-1 down to 1 do
j = random(0..i)
swap a[j], a[i]
done

Initialisera en array a med n elements från en slumpmässigt ordnad kopia av source

a[0] = source[0]
for i from 1 to n-1 do
j = random(0..i)
a[i] = a[j]
a[j] = source[i]
done

[[category:Programmering]]
[[category:C]]
[[category:Linux]]