CODEWITHSUNDEEP
algorithmscalalanguage-agnostichlist
Alban Dericbourg
Alban Dericbourg

Reputation: 1636

Algorithm to define pairs from a list

Christmas is coming: it is time to determine who is going to make a gift to whom. I'm looking for such an algorithm.

Taking a list (1 to 10) for instance, create random pairs ensuring that:

So obviously, a simple shuffle is not enough:

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

Eg:

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

But not (1 makes a gift to itself):

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

I've been thinking to constraints on an HList but:

Upvotes: 1

Views: 90

Answers (4)

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

Foolproof solution: assign indexes to the names at random; pick a random prime number N (other than the number of person if this number is itself a prime) and apply a rotation on the list of indexes N positions (modulo the number of persons).

Java code (any java code is scala code, right?)

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]);
}

Result:

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

Upvotes: 2

jwvh
jwvh

Reputation: 51271

Using a Set will insure no duplicates and, since a Set has no defined order, iterating over it will appear randomized.

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

Then make your round-robin associations.

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)

Upvotes: 1

Alban Dericbourg
Alban Dericbourg

Reputation: 1636

Actually, this simple algorithm should to the trick.

  1. Shuffle the initial list
  2. Associate index i to index i+1 (modulo the size of the list)

This should be random enough for the need.

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)}"))

Result is:

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

It works as long as the list has at least 2 elements.

Upvotes: 0

Pavel
Pavel

Reputation: 1539

just a mock up example: There are some scenarios to look at:

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

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

I am sure this could be optimised.

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 ))

Upvotes: 1

Related Questions