Алгоритм определения пар из списка

Question

Приближается Рождество: пришло время определить, кто собирается сделать подарок кому. Я ищу такой алгоритм.

Принимая список (1 to 10), например, создавать случайные пары, обеспечивающие, что:

• каждый элемент связан с другим элементом;
• Ни один из предметов не связан с самим собой;
• каждый элемент связан один раз и только один раз.

Так, очевидно, простая перетасовка не хватает:

Random.shuffle(1 to 10) 
    .toSeq 
    .zipWithIndex 

Например:

1 -> 2 
2 -> 4 
3 -> 1 
4 -> 3 

Но не (1 делает подарок себе):

1 -> 1 
2 -> 3 
3 -> 4 
4 -> 2 

Я думал о ограничениях на HList, но:

• Я не был в состоянии выразить это
• Это может быть немного излишним (даже если это смешно)
• Там могут быть алгоритмы, которые гарантируют, что «по построению»

Answer 1

На самом деле, этот простой алгоритм должен быть трюком.

1. Перемешать первоначальный список
2. Associate индекс i к индексу i+1 (по модулю размера списка)

Это должно быть достаточно случайным для потребности.

val people = Random.shuffle(Seq("a", "b", "c", "d")) 

val associationIndices = (0 to people.length-1) 
    .map(left => (left, (left + 1) % people.length)) 
    .foreach(assoc => println(s"${people(assoc._1)} -> ${people(assoc._2)}")) 

Результат:

c -> d 
d -> a 
a -> b 
b -> c 

Он работает до тех пор, как список имеет по крайней мере 2 элементов.

Answer 2

Foolproof solution: присваивать индексы именам в случайном порядке; выберите случайное простое число N (отличное от числа человек, если это число само является простым) и примените поворот в списке индексов N позиций (по модулю количества людей).

Java-код (любая Java-код Scala-код, не так ли?)

ArrayList<String> names= 
    new ArrayList<>(Arrays.asList("Ann","Bob","Ed","Kim","Sue","Tom")); 
SecureRandom rng=new SecureRandom(); // better seed it 
String rndNames[]=new String[names.size()]; 
for(int i=0; names.size()>0; i++) { 
    int removeAt=rng.nextInt(names.size()); 
    rndNames[i]=names.remove(removeAt); 
} 
int offset=1; // replace this with a random choice of a 
       // number coprime with rndNames.length, followed by 
       // offset = (randomPrime % rndNames.length) 
       // 1 will do just fine for the offset, it is a valid value anyway 
for(int i=0; i<rndNames.length; i++) { 
    System.out.println(rndNames[i] +"->"+rndNames[(i+offset) % rndNames.length]); 
}  

Результат:

Ann->Sue 
Sue->Bob 
Bob->Ed 
Ed->Tom 
Tom->Kim 
Kim->Ann 

Answer 3

просто макет пример: Есть несколько сценариев, чтобы посмотреть на:

import scala.collection.mutable.ListBuffer 
import scala.util.Random 

val n = 5 
val rnd = new Random() 
val result = ListBuffer.fill(n)((0, 0)) 

Я уверен, что это может быть оптимизировано.

while(result.exists(x => x._1 == 0 && x._2 == 0) == true){ 
    val idx = result.zipWithIndex 
    val p = idx.find(x => x._1._1 == 0 && x._1._2 == 0) 
    p match { 
    case None => Unit// ??? 
    case Some(x) => { 
     val r = rnd.nextInt(n) 
     if (result.exists(r => r._2 == r && x._2 != r) == false) 
     result(x._2) = (x._2 + 1, r + 1) 
    } 
    } 
} 


result.foreach(x => println(x._1 + " : " + x._2)) 

Answer 4

Использование Set не гарантирует наличие дубликатов и, поскольку Set не имеет определенного порядка, итерация по нему будет рандомизирована.

val names = Set("Ann","Bob","Ed","Kim","Sue","Tom") // alphabetical 

Затем сделайте свои круговые ассоциации.

val nameDraw = (names.sliding(2) ++ Iterator(Set(names.last,names.head))) 
        .map(x => x.head -> x.last).toMap 
//nameDraw = Map(Sue -> Ann, Ann -> Tom, Tom -> Bob, Bob -> Ed, Ed -> Kim, Kim -> Sue)