Aqui está o plano de fundo para esta pergunta. Amigos e eu estávamos jogando um jogo em que todos precisam dar algum presente a outras pessoas. Para determinar quem deve dar um presente a quem, decidimos sortear. Mas o problema é que alguém pode acabar dando presentes a si mesmo, o que não é engraçado. Você pode ver que o número esperado de pessoas tão infelizes é 1, então isso acontece com bastante frequência.
Para esse propósito, o arranjo caro parece ser um ótimo ajuste. Se eu conseguir gerar um arranjo justo, posso escolher um arranjo caro e usá-lo para decidir quem dá presentes a quem.
A geração de arranjos aleatórios poderia ser feita com o método Las Vegas. Mas o problema é que ele só esperava tempo de execução polinomial. Então, cheguei a esse problema de encontrar o i-ésimo arranjo. Se eu puder escolher um i aleatoriamente em [1, D_n] e usar algum algoritmo de tempo polinomial de pior caso (eficiente) para obter o i-ésimo arranjo, então está feito.
fonte
Respostas:
Na verdade, essa é uma boa pergunta, mas está mal formulada em sua forma atual. Os algoritmos conhecidos para gerar perturbações aleatórias têm tempo esperado linear, mas talvez seja um problema em aberto encontrar o pior algoritmo de tempo polinomial.
Veja, por exemplo: http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (e slides: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf )
fonte
Por que não, para cada posição i , escolhe aleatoriamente todos os elementos que não sejam i ? Por exemplo, você pode escolher um índice na matriz original de [0..n-2] e, se você obtiver j> = i, usará j + 1 .
fonte