0

给定的是假设 a,b,c,d 的名称列表。我想生成这些名称的秘密圣诞老人允许输出如下..

name secretsanta
a      b
b      d
c      a
d      c

注意：任何输出都是有效的，除非我们为多个名字获得相同的秘密圣诞老人，即

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

以上是不允许的

此外，如果我得到一个输入的正确输出并使用相同的输入再次运行它，我不应该再次得到相同的结果，即 a->b b->d c->a d->c 这不应该立即重复。只有在此后至少显示一次不同的输出后才允许重复。

以下是我尝试过的代码：

do
{
    total_size=ss.santa.size();     
    Collections.shuffle(ss.santa);
    System.out.println("Below is the list of names with their secret santas");
    System.out.println("Participant    Secret Santa");
    Iterator<?> itr=ss.names.iterator();

    while(itr.hasNext())
    {
        String name=(String)itr.next(); 
        String SecretName;
        do
        {
            int rand=r.nextInt(total_size);
            SecretName=ss.santa.get(rand);          
        }while(name.equals(SecretName) || s.contains(SecretName) );
        s.add(SecretName);
        System.out.println(name+"    "+SecretName);         
    }

    s.removeAll(ss.names);
    Collections.shuffle(ss.santa);
    System.out.println("do you want to rerun??");
    System.out.println(" 1-YES 2-NO");
    choice=scn.nextInt();
}while(choice==1);
4

1 回答 1

1

为此目的修改shuffle相当容易：（从 Java API 复制，只是将随机生成器的范围减少了一个以排除将元素保持在同一位置，即更改rnd.nextInt(i)为rnd.nextInt(i-1)，并删除了一些代码）

public static void swap(List<?> list, int i, int j) {
   final List l = list;
   l.set(i, l.set(j, l.get(i)));
}

public static void shuffle(List<?> list) {
   Random rnd = new Random();
   for (int i = list.size(); i > 1; i--)
      swap(list, i-1, rnd.nextInt(i-1));
}

public static void main(String[] args)
{
   List<String> input = Arrays.asList("a","b","c","d");
   System.out.println(input);
   shuffle(input);
   System.out.println(input);
}

现在，您希望每次运行都具有独特的输出这一事实有点困难。这实际上指向一种确定性算法，而不是随机算法。虽然它也可以很容易（虽然不是特别有效）如下完成：（使用与shuffle上面相同的功能）

Set<List> set = new HashSet<List>();
List<String> input = Arrays.asList("a","b","c","d");
set.add(input);
int amountToGenerate = 10;
for (int i = 0; i < amountToGenerate; i++)
{
    ArrayList<String> temp = new ArrayList<String>(input);
    do
    {
        shuffle(temp);
    }
    while (set.contains(temp));
    System.out.println(temp);
    set.add(temp);
}

尽管这将有助于一个人连续多次获得相同的秘密圣诞老人，即使整套​​都是独一无二的。

于 2013-08-23T12:12:03.407 回答