1

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

以列表(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 但是：

  • 我已经无法表达
  • 这可能有点矫枉过正（即使很有趣）
  • 可能有算法可以确保“通过构造”
4

4 回答 4

2

万无一失的解决方案：随机为名称分配索引；选择一个随机素数 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
于 2016-11-26T14:44:15.643 回答
1

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

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 ))
于 2016-11-26T14:51:42.823 回答
1

使用 aSet将确保没有重复，并且由于 aSet没有定义的顺序，因此对其进行迭代将显得随机。

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)
于 2016-11-26T20:03:25.903 回答
0

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

  1. 随机播放初始列表
  2. 将索引关联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 个元素，它就可以工作。

于 2016-11-26T15:19:46.547 回答