Не повторяющиесь случайные строки

[glebast]

Привет ребята.
Я тут забомбил такой вот код:

function GetRandomLine(SL:TStrings):string;
begin
result:=SL1[random(SL1.Count)];
end;

...
per:=StrToIntDef(Edit2.Text, -42);
zad:=edit1.Text;
if edit1.Text=zad then
begin
SL1:=TStringList.Create;
SL1.LoadFromFile('data/web/'+zad+'/1.txt');
for i:=1 to per do
Memo1.Lines.add(GetRandomLine(SL2 ));
end;
...

Но мне захотелось чего-то большего. И я решил сделать так, чтобы случайные строки не повторялись. Но после 3 дней моих усилий я понял что я нечтожество и без вашей помощи у меня ни чего не получиться.

Ребята, будьте добры, помогите пожалуйста.
Я буду очень вам благодарен.

Заранее спасибо!

[DiemonStar]

а Randomize кто ставить будет?

[glebast]

Сообщение от DiemonStar

а Randomize кто ставить будет?

Он зашифрован в "...", просто это на данный момент не так существенно.

[Serge_Bliznykov]

во-первых, Вы зря не воспользовались поиском по форуму - подобные задачи решали на форуме многократно.

во-вторых, существует всего два подхода. Какой выбирать - зависит от конкретных деталей (сколько всего значений имеется, сколько случайных из них надо получить и т.д.).

итак, первый способ.
получаем очередное случайное число. проверяем, было ли такое значение раньше. Повторяем данный цикл (получить случ.число и проверить было ли оно раньше) до тех пор, пока такое значение было. Как только сгенерировалось такое, какого раньше не было - запоминаем это значение и переходим к следующему.
Недостатки метода. Нужна структура, в которой сохраняются сгенерённые ранее случайные числа (в общем случае размерность равна количеству неповторяющихся чисел). При числе неповторяющихся случайных величин равному (или близкому) к общему числу имеющихся для выбора вариантов алгоритм может сильно "тупить" - он постоянно будет попадать на варианты, которые были раньше.

поэтому, если число вариантов, из которых надо выбрать, ограничено, то я бы предложил Вам другой, более эффективный способ.
берём массив, равный числу вариантов. заполняем его значениями от 1-го индекса до максимального, перемешиваем числа в этом массиве. берём от начала массива нужно число значений (они будут и случайными в силу перемешивания, и гарантированно неповторяющимися, т.к. изначально массив был заполнен неповторяющимися значениями). всё. задача решена.


добавлено
по поводу нужный тем тут, на форуме...

например, вот, для затравки две темы.
там есть примеры кода
http://www.programmersforum.ru/showthread.php?t=38802
http://www.programmersforum.ru/showthread.php?t=106614

[glebast]

Ай не, не получается. Вся загвоздка в том, что у меня строки, а не просто числа. И по этому у меня ни чего не выходит.

Может у кого-то есть еще хоть какие нибудь варианты.

[Serge_Bliznykov]

Вся загвоздка в том, что у меня строки, а не просто числа.

SL1[random(SL1.Count)];

задумайтесь над тем, что я выделил.. это же ЧИСЛО.
вот от него и пляшите!

рекомендую применить второй способ (с заполнением и перемешиванием массива)

[DiemonStar]

я бы добавил ещё третий способ:
1) копируем список в отдельный список (если важно сохранить изначальный текст)
2) находим случайную строку и добавляем в список результата
3) удаляем эту строку из исходного списка
4) выполняем с п.2. пока в исходном списке есть строки.

например так:

Dest.Clear;
for I := Source.Item.Count -1 downto 0 do
  begin
     J := Random(I);
     Dest.Append(Source[J]);
     Source.Delete(J); 
  end;

[Serge_Bliznykov]

первое.

glebast, объясните мне это чудо чудное:

  zad:=edit1.Text;
  if edit1.Text=zad then

Вы проверяете, хорошо ли присвоилась строка? Надёжно?!


вот пример решения вашей проблемы через использования массива с перемешиванием:

procedure TForm1.Button1Click(Sender: TObject);
var SL1: TStringList;
  RndStringNumbers: array of integer;
  per, i, k, N, buf : integer;
  zad : string;
begin
  per := StrToIntDef(Edit2.Text, -42);
  zad := edit1.Text;
  Randomize;
{  if edit1.Text = zad then }
  SL1 := TStringList.Create;
  SL1.LoadFromFile('data/web/' + zad + '/1.txt');

  {заполним массив}
  N := SL1.Count;
  SetLength(RndStringNumbers, N);
  for i := 0 to N - 1 do
    RndStringNumbers[i] := i;

  {перемешаем массив случайным образом
     Для (i от 0 до n-2)
        Переставить i-ю карту со случайной картой от i-й до n-й
   }
  for i := 0 to N - 2 do
  begin
    k := Random(N - i) + i;
    if k <> i then begin
      buf := RndStringNumbers[i];
      RndStringNumbers[i] := RndStringNumbers[k];
      RndStringNumbers[k] := buf;
    end;
  end;

  {очистим массив, куда будем помещать результат}
  Memo1.Lines.Clear;

  {возьмём нужно число случайных строк}
  if per>N then per:=N;
  for i := 0 to per-1 do
     Memo1.Lines.add( SL1[ RndStringNumbers[i] ] );

  {освободим занятую память...}   
  SetLength(RndStringNumbers, 0);
  FreeAndNil( SL1 );

end;