适当的随机播放:代码堵塞[2014]

Question

我想在第1A轮中与Code Jam问题C分享,它叫做Proper Shuffle.我很了解你的解决方案.

这是问题所在:

大小N的排列是N个数字的序列,每个数字在0和N-1之间,其中每个数字恰好出现一次.它们可能以任何顺序出现.

有很多(N因素,确切地说,但在这个问题上并不重要)大小为N的排列.有时我们只想随机选择一个,当然我们想要随机选择一个:每个排列大小为N应该具有相同的被选择概率.

这是实现该目标的可能算法之一的伪代码(我们将其称为下面的好算法):

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(k .. N-1)
  swap(a[k], a[p])

在上面的代码中,randint(a ... b)返回a和b之间的均匀随机整数.

这是单词中的相同算法.我们从身份置换开始:从0到N-1的所有数字按递增顺序写入.然后,对于0和N-1之间的每个k(包括0和N-1),我们在k和N-1之间选择一个独立的均匀随机整数pk,包括在内,并在我们的排列中交换位置k(从0开始)的元素与元素at位置pk.

这是N = 4的示例.我们从身份排列开始:

0 1 2 3

现在k = 0,我们选择0到3之间的随机p0,包括0和3.假设我们选择了2.我们交换第0和第2个元素,我们的排列变为:

2 1 0 3

现在k = 1,我们选择1到3之间的随机p1,包括1和3.假设我们再次选择2.我们交换第一和第二元素,我们的排列变为:

2 0 1 3

现在k = 2,我们选择2和3之间的随机p2,包括两者.假设我们选择了3.我们交换了第二和第三个元素,我们的排列变为:

2 0 3 1

现在k = 3,我们选择3到3之间的随机p3,包括3和3.唯一的选择是3.我们交换第3和第3个元素,这意味着排列不会改变:

2 0 3 1

这个过程现在结束了,这是我们的随机排列.

还有许多其他算法可以统一产生随机排列.然而,还有许多算法可以生成看起来与此算法非常相似的随机置换,但不是统一的 - 某些置换比其他算法更可能由这些算法生成.

这是一种不好的算法.采用上面的好算法,但是在每个步骤中,不是在k和N-1之间随机选择pk,而是在0和N-1之间随机选择它.这是一个很小的变化,但现在一些排列比其他排列更容易出现!

这是这个算法的伪代码(我们称之为下面的坏算法):

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(0 .. N-1)
  swap(a[k], a[p])

在每个测试用例中,您将获得以下列方式生成的排列:首先,我们选择上述优良或不良算法,每种算法的概率为50%.然后,我们使用所选算法生成置换.您能通过查看排列来猜测选择哪种算法吗？

解决这个问题

Code Jam有点不寻常.您将获得每个N = 1000个数字的T = 120个排列,并且应该为每个排列打印答案 - 这部分与往常一样.但是,您不需要将所有答案都正确!如果您对至少G = 109个案例的答案是正确的,那么您的解决方案将被视为正确.但是,您必须遵循输出格式,即使对于答案结果不正确的情况也是如此.在任何情况下唯一可能出错的事情,但仍然允许你被判断为正确,正在交换好的坏事,反之亦然; 但是对于每种情况,你仍然应该打印GOOD或BAD.

保证给出的排列是根据上述方法生成的,并且它们是彼此独立生成的.

这个问题涉及随机性,因此即使最好的解决方案也不会对某个输入做出正确的猜测,因为好的和坏的算法都可以产生任何排列.因此,此问题没有大输入,并且只有小输入,如果您认为不幸,可以再次尝试.请注意,如果您稍后解决该输入,则错误提交通常会有4分钟的惩罚,即使您错误的唯一原因是机会.

根据我们对这个问题的经验,这确实发生了(因为偶然而得到了错误的答案); 因此,如果您确信您的解决方案应该正常工作,但它失败了,那么尝试使用失败的相同解决方案可能是一种合理的策略.

祝好运!

输入

输入的第一行给出了测试用例的数量T(总是120).每个测试用例包含两行:第一行包含单个整数N(始终为1000),下一行包含N个空格分隔的整数 - 使用两种算法之一生成的排列.

产量

对于每个测试用例,输出一行包含"Case #x:y",其中x是测试用例编号(从1开始),y是"GOOD"或"BAD"(不带引号).如果您猜测排列是由问题陈述中描述的第一个算法生成的,则应输出"GOOD";如果您猜测排列是由问题陈述中描述的第二个算法生成的,则应输出"BAD".

范围

T = 120
G = 109
N = 1000

置换中的每个数字将在0和N-1(包括)之间,并且从0到N-1的每个数字将在置换中恰好出现一次.

样品

Input 

2
3
0 1 2
3
2 0 1

Output 

Case #1: BAD
Case #2: GOOD

注意

样本输入不符合问题陈述的限制 - 实际输入会更大.

Answer 1

对于你从这个破碎的随机洗牌中获得什么分布所做的出色研究呢？,以下测试工作得相当好.计算perm [k]> k的索引数k.如果数量超过N/2 +一些小数量,打印BAD.否则,打印好.

这是我的Java实现,它合理地传递.我手动调整了阈值,因此可能有更好的设置.

public class UniformOrNonuniform {
    public static void main(String[] args) {
        java.util.Random source = new java.security.SecureRandom();
        int successes = 0;
        int[] perm = new int[1000];
        for (int i = 0; i < 120; i++) {
            identityPerm(perm);
            boolean uniform = source.nextBoolean();
            if (uniform) {
                nextUniformPerm(source, perm);
            } else {
                nextNonuniformPerm(source, perm);
            }
            if (isUniformPerm(perm) == uniform) {
                successes++;
            }
        }
        System.out.println(successes);
    }

    private static void identityPerm(int[] perm) {
        for (int k = 0; k < perm.length; k++) {
            perm[k] = k;
        }
    }

    private static void nextUniformPerm(java.util.Random source,
                                        int[] perm) {
        for (int k = 0; k < perm.length; k++) {
            swap(perm, k, k + source.nextInt(perm.length - k));
        }
    }

    private static void nextNonuniformPerm(java.util.Random source,
                                           int[] perm) {
        for (int k = 0; k < perm.length; k++) {
            swap(perm, k, source.nextInt(perm.length));
        }
    }

    private static void swap(int[] perm, int i, int j) {
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }

    private static boolean isUniformPerm(int[] perm) {
        int score = 0;
        for (int k = 0; k < perm.length; k++) {
            if (perm[k] > k) {
                score++;
            }
        }
        return score <= 512;
    }
}