목록에서 쌍을 정의하는 알고리즘

크리스마스가오고 있습니다 : 누구에게 선물을 줄지 결정해야합니다. 나는 그런 알고리즘을 찾고있다. 그 보장 목록 예를 들어 (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에 대한 제약을 생각하고 있었지만 :

나는 그것을 표현하지 못하고 그것은 수 있습니다
는 "건설에 의해"확인 알고리즘이있을 수 있습니다

출처

2016-11-26 Alban Dericbourg

조건이 충족 될 때까지 셔플을 반복하면 간단하게 두세 번만 시도 할 수 있습니다. –

그게 실제로 옵션입니다 : 아마 작동합니다. 그러나 호기심 때문에, 나는 좀 더 우아한 것이 있는지 궁금해하고있었습니다. –

@PeterdeRivaz는 전체 셔플을 반복 할 필요가 없습니다. 내가 일하는 곳에서 우리는 비니를 사용합니다. 모든 이름을 던지십시오. 모두가 하나를 선택합니다. 너가 너 자신에게 선물을 얻으면, 너의 이름을 다시두고 다른 것을 고르 십시요. –

실제로이 간단한 알고리즘은 트릭을 사용해야합니다.

은 초기 목록을 인덱스 i+1-
준 인덱스 i (목록의 크기를 모듈로)

이 필요 충분한 임의해야 셔플.

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

결과이다 : 그것은 한 목록이 최소 2 개 요소가로 작동

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

출처

2016-11-26 15:19:46

절대 안전한 솔루션 : 임의로 인덱스에 이름을 할당하십시오. 무작위 소수 N (이 숫자 자체가 소수 인 경우 사람 수 제외)을 선택하고 인덱스 N 목록 (사람 수를 기준으로) 목록에 회전을 적용합니다.

자바 코드 (모든 자바 코드를 잘 스칼라 코드?)

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-26 14:44:15

간단한 예제를 열거 할 수 있습니까? –

단지 모의까지 예 : 가 보는 몇 가지 시나리오가 있습니다

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-26 14:51:42 Pavel

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)

출처

2016-11-26 20:03:25 jwvh

목록에서 쌍을 정의하는 알고리즘

답변

관련 문제