Создание массива частично случайных булевых значений на основе определенных критериев

Question

Я пытаюсь создать случайные данные на основе некоторых критериев. Я застрял в том, как начать, поэтому у меня нет кода.

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

Итак, подходит к проблеме, позволяет сказать, что у нас есть это существующий данные:

Total - 10 
Won - 7 
Lost - 3 
Longest Winning Streak - 5 
Longest Losing Streak - 2 

Теперь мне нужно, чтобы сгенерировать массив случайных булевых значений (true, представляющей победу и false, представляющий убыток), который выполняет вышеуказанные критерии.

Таким образом, в этом случае выход может быть любым из следующих:

0011011111 
1111101100 
1010011111 
.......... 

Его полоса часть, которая беспокоит меня. Если бы не полоса, я мог бы сгенерировать семь 1(s) и три 0(s), а затем случайным образом перетасовать их.

Примечание: Я бы предпочел решения в C#, VB.NET, JavaScript или Python, но любой язык приветствуется.

Answer 1

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

class Program 
{ 
    static int len = 10; 
    static int win = 7; 
    static int lws = 5; 
    static int lls = 2; 

    static Random rnd = new Random(); 

    static void Main(string[] args) 
    { 
     int genSz = 15; 
     var generation = new List<Chromosome>(); 
     Helper.Repeat(() => generation.Add(new Chromosome()), genSz); 

     int gen = 1; 
     while (generation.First().Fitness != 0) 
     { 
      //procreation 
      Helper.Repeat(() => { 
       int x1 = rnd.Next(genSz/2); 
       int x2 = rnd.Next(genSz); 
       generation.Add(new Chromosome(generation[x1], generation[x2])); 
      }, genSz); 
      //selection 
      generation = generation.OrderBy(x => x.Fitness).Take(genSz).ToList(); 
      Console.WriteLine("GENERATION " + gen++); 
      foreach (var x in generation) 
      { 
       Console.WriteLine(x); 
      } 
      Console.ReadLine(); 
     } 
     Console.ReadLine(); 
    } 

    class Chromosome 
    { 
     bool[] genes = new bool[len]; 

     public Chromosome() { } 

     public Chromosome(Chromosome p1, Chromosome p2) 
     { 
      //crossingover 
      rnd.Shuffle(ref p1, ref p2); //may reorder parents or not 
      var x = rnd.Next(len); 
      Array.Copy(p1.genes, 0, genes, 0, x); 
      Array.Copy(p2.genes, x, genes, x, len - x); 
      //mutation 
      if (rnd.Flip()) 
      { 
       x = rnd.Next(len); 
       genes[x] = !genes[x]; 
      } 
     } 
     public int Fitness 
     { 
      get 
      { 
       int w = genes.Count(g => g); 
       int l = len - w; 
       int ws = genes.LongestStreak(g => g); 
       int ls = genes.LongestStreak(g => !g); 
       return Math.Abs(w - win) + Math.Abs(lws - ws) + Math.Abs(lls - ls); 
      } 
     } 
     public override string ToString() 
     { 
      return "[" + new string(genes.Select(g => g ? '*' : '.').ToArray()) + "] " + Fitness.ToString(); 
     } 
    } 
} 

public static class Helper 
{ 
    public static bool Flip(this Random rnd) => rnd.Next(2) == 0; 
    public static void Shuffle<T>(this Random rnd, ref T a, ref T b, bool allowNoChange = true) 
    { 
     if (allowNoChange && rnd.Flip()) return; //no reordering 
     T tmp = a; a = b; b = tmp; 
    } 

    public static int LongestStreak<T>(this IEnumerable<T> sequence, Predicate<T> selector) 
    { 
     int current = 0; 
     int longest = 0; 
     foreach (T x in sequence) 
     { 
      if (selector(x)) 
      { 
       current++; 
       if (current > longest) longest = current; 
      } 
      else 
      { 
       current = 0; 
      } 
     } 
     return longest; 
    } 

    public static void Repeat(this Action action, int N) 
    { 
     for (int n = 0; n < N; n++) action(); 
    } 
} 

Второй вариант - перебор. На самом деле может быть быстрее, чем генетический alg на эту задачу. Также вы можете получить с ним все возможные варианты.

class Program 
{ 
    static void Main(string[] args) 
    { 
     var res = new[] { true, false }.Words(10).Where(w => { 
      return 
       w.Count(g => g) == 7 && 
       w.LongestStreak(g => g) == 5 && 
       w.LongestStreak(g => !g) == 2; 
     }); 
     foreach (var v in res) 
     { 
      foreach (var b in v) 
      { 
       Console.Write(b ? "*" : "."); 
      } 
      Console.WriteLine(); 
     } 
     Console.WriteLine(res.Count()); 
     Console.ReadLine(); 
    } 
} 

public static class Helper 
{ 
    public static IEnumerable<IEnumerable<T>> Words<T>(this IEnumerable<T> alphabet, int len) 
    { 
     foreach (var l in alphabet) 
     { 
      if (len == 1) 
      { 
       yield return l.Yield(); 
      } 
      else 
      { 
       foreach (var w in alphabet.Words(len - 1)) 
       { 
        yield return w.Prepend(l); 
       } 
      } 
     } 
    } 

    public static IEnumerable<T> Yield<T>(this T item) 
    { 
     yield return item; 
    } 

    static IEnumerable<T> Prepend<T>(this IEnumerable<T> rest, T first) 
    { 
     yield return first; 
     foreach (var item in rest) 
      yield return item; 
    } 

    public static int LongestStreak<T>(this IEnumerable<T> sequence, Predicate<T> selector) 
    { 
     int current = 0; 
     int longest = 0; 
     foreach (T x in sequence) 
     { 
      if (selector(x)) 
      { 
       current++; 
       if (current > longest) longest = current; 
      } 
      else 
      { 
       current = 0; 
      } 
     } 
     return longest; 
    } 
} 

Answer 2

Мое предложение было бы использовать алгоритм для выбора k битов (ваш won номер) от длина- n (ваш total номер) строки. Здесь я использую kbits(n, k) function, написанный @foglebird. Затем вы можете отфильтровать нежелательные перестановки, используя понимание списка.

import itertools 

def kbits(n, k): 
    result = [] 
    for bits in itertools.combinations(range(n), k): 
     s = ['0'] * n 
     for bit in bits: 
      s[bit] = '1' 
     result.append(''.join(s)) 
    return result 

total = 10 
won = 7 
lost = 3 
max_win = 5 
max_lose = 2 

answer = [x for x in kbits(total, won) if '1'*(max_win+1) not in x and '0'*(max_lose+1) not in x] 

Answer 3

У меня был ответ, и я заметил, что мне не хватало некоторых ключевых требований. Я добавил и изменил некоторые вещи для устранения этих недостающих элементов.

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

шаги используются:

• Выберите случайное место для самой длинной полосы (Win в примере)
• Кронштейн полоса с потерями, чтобы предотвратить расширение его при установке объедки
• Найти индексы с достаточно последовательных слотов для удержания полосы потерь
• Выберите случайную и установите полосу потерь (возвращается, если их нет)
• Установите все остатки как Not the value at n-1 на избегать продления или создания новой полосы

Таким образом, становится хитом или пропуском, верны ли WinCount и LossCount. Кажется, легче наткнуться, чем полосы правильного размера. Метод оболочки проверяет результат на отклонение и повтор. При заданных значениях он обычно находит победителя в первые 10 или около того раз.

---

Метод ядра для построения строкового представления, и помощник:

' ToDo change to return Bool() = string is easier to read 
Private Function FarhamStreaks(winStrk As Int32, loseStrk As Int32, total As Int32) As String 

    ' -1 == not set 
    Dim result = Enumerable.Repeat(-1, total).ToArray 

    ' set longest streak first 
    Dim wNDX = RNG.Next(0, total + 1 - winStrk) 
    For n As Int32 = 0 To winStrk - 1 
     result(wNDX + n) = 1 
    Next 
    ' bracket with losers so the w streak cant extend 
    If wNDX > 0 Then result(wNDX - 1) = 0 
    If wNDX + winStrk < result.Length - 1 Then result(wNDX + winStrk) = 0 

    ' look for eligible consecutive starting slots 
    ' might be none 
    Dim lossNdx As New List(Of Int32) 
    For n As Int32 = 0 To result.Count - 1 
     Dim count = CountConsecutiveLooserSlotsFrom(n, result) 

     If (n + 1) < result.Count AndAlso count >= loseStrk Then 
      lossNdx.Add(n) 
     End If 
    Next 

    If lossNdx.Count = 0 Then 
     ' do over 
     ' the code has never gotten here 
     ' but depends on the mix of values 
     Return "" 
    End If 

    ' set losses 
    Dim lNdx = lossNdx(RNG.Next(0, lossNdx.Count)) 
    For n As Int32 = 0 To loseStrk - 1 
     result(lNdx + n) = 0 
    Next 

    ' set the leftovers based on next value to avoid 
    ' extending streaks 
    For n As Int32 = 0 To result.Length - 1 
     If result(n) = -1 Then 
      If n > 0 Then 
       result(n) = If(result(n - 1) = 0, 1, 0) 
      Else 
       result(n) = If(result(n + 1) = 0, 1, 0) 
      End If 
     End If 
    Next 

    Dim resultString = String.Join(",", result) 

    ' convert to boolean 
    Dim realResult(total) As Boolean 
    For n As Int32 = 0 To total - 1 
     realResult(n) = Convert.ToBoolean(result(n)) 
    Next 

    Return resultString 
End Function 

' find candidate slots for the shorter streak: 
Private Function CountConsecutiveLooserSlotsFrom(ndx As Integer, theArray As Int32()) As Int32 
    Dim count As Int32 = 1 ' including ndx 

    For n As Int32 = ndx To theArray.Length - 2 
     If theArray(n) <> 1 AndAlso theArray(n + 1) <> 1 Then 
      count += 1 
     Else 
      Exit For 
     End If 
    Next 
    Return count 
End Function 

метод для проверки результата кандидата (и показатели эффективности):

Private Function MakeFarhamStreak(wins As Int32, winStreak As Int32, 
            lossStreak As Int32, 
            total As Int32) As String 
    Const MaxTries As Int32 = 999 
    Dim losses = (total - wins) 
    Dim reverse As Boolean = (lossStreak > winStreak) 
    Dim candidate As String 
    Dim sw As New Stopwatch 
    Dim pass, fail As Int32 
    Dim count As Int32 

    sw.Start() 

    For n As Int32 = 0 To MaxTries 

     If reverse Then 
      candidate = FarhamStreaks(lossStreak, winStreak, total) 
      ' to do: un-reverse (Not) the results - 
     Else 
      candidate = FarhamStreaks(winStreak, lossStreak, total) 
     End If 

     Dim result = candidate.Split(","c) 

     ' test win count 
     count = candidate.Where(Function(f) f = "1").Count 
     If count <> wins Then 
      fail += 1 
      Continue For 
     End If 

     ' test loss count 
     count = candidate.Where(Function(f) f = "0").Count 
     If count <> losses Then 
      fail += 1 
      Continue For 
     End If 

     Dim tmp = candidate.Replace(","c, "") 

     ' test win streak size 
     Dim wstreaks = tmp.Select(Function(c, i) tmp.Substring(i). 
             TakeWhile(Function(q) q = c AndAlso q = "1"). 
             Count()). 
            Max 
     If wstreaks <> winStreak Then 
      fail += 1 
      Continue For 
     End If 

     Dim lstreaks = tmp.Select(Function(c, i) tmp.Substring(i). 
          TakeWhile(Function(q) q = c AndAlso q = "0"). 
          Count()). 
         Max 
     If lstreaks <> lossStreak Then 
      fail += 1 
      Continue For 
     End If 

     pass += 1 
     If pass = 1 Then 
      Console.WriteLine("First Pass in {0}ms (try # {1} = {2})", 
           sw.ElapsedMilliseconds, n, candidate) 
      ' normally, return at this point 
     End If 
    Next 

End Function 

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

результаты:

Первый проход в 18мс (попробуйте # 4 = 1,1,1,1,1,0,0,1,0,1)
Всего FAILURES 753 75,38%
Всего Пасс 247 24,72%
Общее время 999 кандидатов 29ms

он нашел первое прохождение значения на Ьгу # 4 - с 10, 7W, 5Ws, 2LS значения обычно находит один в первом 10.