从列表中定义对的算法

Question

圣诞节快到了：是时候决定谁要给谁送礼物了。我正在寻找这样的算法。

以列表(1 to 10)为例，创建随机对确保：

每个项目都与另一个项目关联；
none 个项目与其自身相关联；
每个项目只关联一次。

很明显，简单的洗牌是不够的：

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，但是：

一直表达不出来
这可能有点矫枉过正（即使它很有趣）
可能有算法可以确保 "by construction"

Answer 1

万无一失的解决方案：随机为名称分配索引；选择一个随机素数 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 2

只是一个模拟示例：有一些场景可以看：

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 3

实际上，这个简单的算法应该可以解决问题。

随机播放初始列表
将索引 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 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)

从列表中定义对的算法

Algorithm to define pairs from a list

language-agnostic

algorithm

scala

hlist