Перемешивание очень длинной последовательности. Тасование Фишера-Йетса

Posted by obzor under c/c++

Стоит задача случайно перемешать последовательность символов длинной около 70 млн символов. Подскажите как это проще всего реализовать?

Serge_Bliznykov

я же правильно понимаю, у Вас есть последовательность символов, нужно эти символы переставить в последовательности случайным образом, так?
где символы хранятся? если в массиве, то перемешать можно легко за один проход по массиву (ну, разумеется, будет ~70*2 миллионов перестановок.

перемешать можно по алгоритму отсюда

Arigato

Набросал пример на Си, реализующий алгоритм тасование Фишера-Йетса:

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>

int main(){
	const int n=100;
	int mas[n];
	
	srand(time(NULL));
		
	for(int i=0; i<n; i++)
		mas = i;
		
	for(int i=n-1; i>0; i--){
		int k=rand()%(i+1);
		int tmp=mas;
		mas=mas[k];
		mas[k]=tmp;
	}
		
	for(int i=0; i<n; i++)
		printf("%d ", mas);
	
	getch();
	return 0;
}

Но стоит отметить, что в чистом Си rand() дает случайное число 0..32767, то есть для 70 млн неприменим.

тема на форуме

Похожие статьи

• Функция, которая на вход принимает строку и в качестве результата возвращает ее копию
• Найти в массиве и вывести значение наиболее часто встречающегося элемента