RandomCut Ekleme/Eleme, Dizi Uçlarında Rasgele Kesişme

October 17, 2021

Posted by Salih Dincer

Permalink

Salih Dincer

Permalink

Merhaba Ali Hocam,

Hata var mı ya da normal bir sonuç mu? Çünkü 1 milyonluk döngüde denedim ve hiç assertion failure vermedi! Bu nasıl olur bilyorum; farklı randomize sıralama ama kenardaki elemanlar aynı kalıyor...

Başlıkta tam ifade edemedim; buna seçme/çekme (diziden eksiltme) de diyebiliriz!

Bir dizimiz (input_PrimeNumbers) olsun. Eleman sayısı (5 de olabilir) önemsiz...

Output(): İlkinde diziye rasgele ekleme yapıyoruz. (1 kere karıştırdıktan sonra)
Input(): İkincisinde diziden rasgele ELEME (geleneksel yöntemler kullanarak) yapıyoruz...

Nedense her seferinde (son satırdaki assert) oluyor! Son eleman girdiğinde ve kaldığında ikisi de eşittir, neden?

/* D Compiler: DMD 2.0.83
 *
 * RandomCut.d (17.10.2021)
 */

  import std.algorithm.mutation : remove;
  import std.stdio, std.range, std.random;

class RandomCut(T) {
  T[] array;
  size_t ind;
  Random rnd;

  this(T[] array, Random random) {
    ind = array.length;
    rnd = random;
    this.array = array.randomShuffle(rnd);
  }

  T Output() {
    ind--;
//    auto r = array.randomShuffle(rnd).take(1)[0];/*
    auto r = array[ind];//*/
    return r;
  }

  void Input(Random random) {
    auto l = array.length;
    while(--l) {
//      array.remove(uniform(0, l + 1, rnd));/*
      size_t pos = array.choice(random);
      for(size_t c = pos - 1; c < l; c++) {
        array[c] = array[c + 1];
      }//*/
      array.length = l;
      array.writeln;
    }
  }

  bool empty() { return ind?1:0; }
}

void main()
{
  auto input_PrimeNumbers = [ 2, 3, 5, 7, 11, 13,
  17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
  67, 71, 73, 79, 83, 89, 97 ];/*, 101, 103, 107, 109,
  113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
  173, 179, 181, 191, 193, 197, 199, 211, 223, 227 ];//*/

  int[] output_AppendList;
  auto test = new RandomCut!int
  (
    input_PrimeNumbers.dup,
    Random(unpredictableSeed)  // only for Output()
  );

  do
  {
    output_AppendList ~= test.Output();
    output_AppendList.writeln;
  } while(test.empty);

  test.Input(Random(unpredictableSeed));

  auto t1 = output_AppendList[$-1];  // get last element
  auto t2 = test.array[0];  // get first element
  t1.writeln(" : ", t2);

  assert(t1 == t2); // why!
} /* ÇIKTISI:
[7]
[7, 2]
[7, 2, 11]
[7, 2, 11, 3]
[7, 2, 11, 3, 11]
[11, 7, 5, 2]
[11, 7, 5]
[11, 7]
[11]
11 : 11
*/

Aslında ne zaman geleneksel yöntemden (döngü içinde kaydırma) uzaklaşıp std.algorithm.mutation'daki remove() kullanılırsa Input() ve Output() birbirleri ile kesişmiyor
yani assert() hata veriyor. Neden acaba?

Teşekkürler...

Forums