Sobre a série
Primeiro, você pode tratar isso como qualquer outro desafio de código de golfe e respondê-lo sem se preocupar com a série. No entanto, existe uma tabela de classificação em todos os desafios. Você pode encontrar a tabela de classificação junto com mais informações sobre a série no primeiro post .
Embora eu tenha várias idéias alinhadas para a série, os desafios futuros ainda não estão definidos. Se você tiver alguma sugestão, informe-me na postagem da sandbox relevante .
Buraco 3: Partições Inteiras
Hora de aumentar um pouco a dificuldade.
Uma partição de um número inteiro positivo n
é definida como um conjunto múltiplo de números inteiros positivos que somam n
. Como exemplo n = 5
, se existirem as seguintes partições:
{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}
Note-se que estes são multisets, portanto, não há fim para eles, {3,1,1}
, {1,3,1}
e {1,1,3}
são todos considerados idênticos.
Sua tarefa é, dada n
, gerar uma partição aleatória de n
. Aqui estão as regras detalhadas:
A distribuição das partições produzidas deve ser uniforme . Ou seja, no exemplo acima, cada partição deve ser retornada com probabilidade 1/7.
Obviamente, devido às limitações técnicas dos PRNGs, a uniformidade perfeita será impossível. Com o objetivo de avaliar a uniformidade de seu envio, as seguintes operações serão consideradas como produzindo distribuições perfeitamente uniformes:
- Obtenção de um número de um PRNG (acima de qualquer intervalo), que está documentado para ser (aproximadamente) uniforme.
- Mapear uma distribuição uniforme sobre um conjunto maior de números para um conjunto menor via módulo ou multiplicação (ou alguma outra operação que distribua valores uniformemente). O conjunto maior deve conter pelo menos 1024 vezes o maior número possível de valores que o conjunto menor.
Como as partições são multisets, você pode devolvê-las em qualquer ordem, e essa ordem não precisa ser consistente. No entanto, para fins da distribuição aleatória, a ordem é ignorada. Ou seja, no exemplo acima
{3,1,1}
,{1,3,1}
e{1,1,3}
juntos devem ter uma probabilidade de 1/7 de serem retornados.- Seu algoritmo deve ter um tempo de execução determinístico. Em particular, você não pode gerar multisets aleatórios e rejeitá-los se não somarem
n
. - A complexidade de tempo do seu algoritmo deve ser polinomial
n
. Em particular, você não pode simplesmente gerar todas as partições e selecionar uma aleatória (já que o número de partições aumenta exponencialmenten
). Você pode supor que o PRNG que você está usando pode retornar valores uniformemente distribuídos em O (1) por valor. - Você não deve usar nenhuma função interna que resolva esta tarefa.
Você pode escrever um programa completo ou uma função e obter entrada via STDIN ou alternativa mais próxima, argumento de linha de comando ou argumento de função e produzir saída via valor de retorno ou imprimindo em STDOUT (ou alternativa mais próxima).
Você pode assumir que n ≤ 65
(de modo que o número de partições seja menor que 2 21 ). A saída pode estar em qualquer lista conveniente ou inequívoca ou formato de string.
Se você enviar uma função, considere também fornecer um pequeno programa de teste que chame a função várias vezes e imprima os resultados. Tudo bem se os parâmetros tiverem que ser ajustados no código. Isso é apenas para que as pessoas possam verificar se a solução é pelo menos aproximadamente uniforme.
Isso é código de golfe, então a submissão mais curta (em bytes) vence. E, é claro, o menor envio por usuário também entrará na tabela geral de líderes da série.
Entre os melhores
O primeiro post da série gera uma tabela de classificação.
Para garantir que suas respostas sejam exibidas, inicie todas as respostas com um título, usando o seguinte modelo de remarcação:
# Language Name, N bytes
onde N
está o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(O idioma não é mostrado no momento, mas o snippet exige e o analisa, e eu posso adicionar um cabeçalho por idioma no futuro.)
fonte
u/\. y
breve?GolfScript, 90 bytes
Demonstração online
Esta é uma adaptação do meu código de contagem de partições (mais simples) que, em vez de apenas rastrear uma contagem, rastreia uma contagem e um dos elementos contados selecionados uniformemente.
Comparação lado a lado dos dois:
Diferenças:
~
é porque este é um programa e não um trecho.[1.]
substituição1
corresponde à mudança no que é rastreado.{(\{)}%+}%
incrementa cada elemento nessa partição e os{1+}%
adiciona1
à partição.0
torna-se[0]
(jogado para1,
) como parte da mudança no que é rastreado, mas, como precisa permanecer uma matriz quando anexada a outra, precisa do extra[ ]
.{+}*
se torna uma seleção ponderada das partições, combinada com a soma de sua contagem.(;`
remove a contagem da saída e coloca a partição em um bom formato.Estrutura de teste
Ajuste o 7000 inicial se você quiser executar um número diferente de tentativas. Observe que isso é muito lento para uma demonstração online.
fonte
Java,
285267 bytesEsse é o mesmo método da resposta do TheBestOne, mas usa uma matriz simples em vez de um mapa. Além disso, em vez de retornar a partição aleatória como a
List
, ela as imprime no console.Abaixo está um programa de teste que o executa 100000 vezes. Por exemplo
n=5
, todos os conjuntos estavam dentro de 0,64% de um 1/7 perfeito na minha última execução.fonte
Math.min
chamada para baixo para(k<n?k:n)
, você pode ir mais longe, deixando de lado-a inteiramente e apenas fazendo duas verificações:b<k&b++<n
. Você também pode abandonar facilmente an>0
parte do loop condicional (já quen>0&b<n
reduz ab<n
quandob
é garantido não negativo).int
declaração em separado também.CJam,
6456 bytesVocê pode testá-lo com este script:
Explicação
fonte
Pitão, 64 bytes
Usa /programming//a/2163753/4230423, exceto que a) Nenhum cache desde que Pyth memoriza automaticamente, b) Imprime cada um em vez de anexar à lista ec) é traduzido para Pyth.
Vou postar uma explicação disso quando tiver tempo, mas aqui está o código python correspondente:
Edit: Eu finalmente comecei a fazer a explicação:
fonte
Oitava, 200
Ungolfed:
Construa uma matriz quadrada em que cada célula (m, n) reflita o número de partições
m
cujo maior número én
, de acordo com o extrato de Knuth @feersum, tão gentilmente citado. Por exemplo,5,2
nos dá 2 porque existem duas partições válidas2,2,1
e2,1,1,1
.6,3
nos dá 3 para3,1,1,1
,3,2,1
e3,3
.Agora podemos encontrar deterministicamente a partição p'th. Aqui, estamos gerando
p
como um número aleatório, mas você pode alterar um pouco o script, assimp
como um parâmetro:Agora podemos mostrar deterministicamente que cada resultado depende exclusivamente de p:
Assim, voltando ao original onde p é gerado aleatoriamente, podemos ter certeza de que cada resultado é igualmente provável.
fonte
(2,2,1)
e(2,1,1,1,1)
(já que as duas que você listou têm números maiores que2
).2
. Eu quis dizer o último.R, 198 bytes
Ungolfed:
Ele segue a mesma estrutura da ótima solução do @ dcsohl no Octave e, portanto, também é baseado no extrato de Knuth publicado pelo @feersum.
Editarei isso mais tarde, se puder encontrar uma solução mais criativa em R. Enquanto isso, qualquer entrada é bem-vinda.
fonte
Java, 392 bytes
Ligue com
a(n)
. Retorna umList
deInteger
sRecuado:
Adaptado de /programming//a/2163753/4230423 e golfed
Como isso funciona: Podemos calcular quantas partições de um número inteiro n existem no tempo O ( n 2 ). Como efeito colateral, isso produz uma tabela de tamanho O ( n 2 ) que podemos usar para gerar a k- ésima partição de n , para qualquer número inteiro k , em O ( n ) tempo.
Então vamos total = o número de partições. Escolha um número aleatório k de 0 ao total - 1. Gere a k- ésima partição.
Como sempre , sugestões são bem-vindas :)
fonte
Python 2, 173 bytes
Recursivamente faz um dicionário
d
, com as teclask
que representam um par(n,m)
pork=67*n+m
(usando o garantidon<=65
). A entrada é o tuplo do número de partição den
emm
partes, e uma tal partição aleatória. As contagens são calculadas pela fórmula recursiva (obrigado ao feersum por indicá-lo)f(n,m) = f(n-1,m-1) + f(n,n-m)
,e a partição aleatória é atualizada escolhendo um dos dois ramos com probabilidade proporcional à sua contagem. A atualização é feita adicionando-se anexando a
1
para o primeiro ramo e incrementando cada elemento para o segundo.Eu tive muitos problemas para obter valores fora dos limites
m
en
dar contagens zero. No começo, usei um dicionário que possui como padrão uma contagem de 0 e uma lista vazia. Aqui, estou usando uma lista e preenchendo-a com esta entrada padrão. Índices negativos fazem com que a lista seja lida a partir do final, o que fornece uma entrada padrão que nunca chegou ao fim como nunca alcançada, e os envolvimentos tocam apenas uma região em quem>n
.fonte
Código da máquina 80386, 105 bytes
Hexdump do código:
Como uma função de C:
void random_partition(int n, int result[]);
. Retorna o resultado como uma lista de números no buffer fornecido; não marca o fim da lista de forma alguma, mas o usuário pode descobrir o final acumulando os números - a lista termina quando a soma é igual an
.Como usar (no Visual Studio):
Exemplo de saída (com n = 64):
Isso requer muitas explicações ...
Claro que usei o algoritmo que todo mundo também usou; não havia escolha com o requisito sobre complexidade. Portanto, não preciso explicar muito o algoritmo. De qualquer forma:
Eu denoto pelo
f(n, m)
número de particionamentos den
elementos usando partes não maiores quem
. Eu os armazeno em uma matriz 2-D (declarada em C comof[65][64]
), onde está o primeiro índicen
e o segundom-1
. Eu decidi que apoiarn=65
era demais, então o abandonei ...Aqui está o código C que calcula esta tabela:
Esse código possui um estilo ofuscado, portanto pode ser convertido para linguagem assembly facilmente. Ele calcula os elementos até
f(n, n)
, que é o número de particionamentos den
elementos. Quando esse código é concluído, a variável temporáriac
contém o número necessário, que pode ser usado para selecionar um particionamento aleatório:Posteriormente, isso
index
é convertido no formato necessário (lista de números) usando a tabela gerada.Este código também é otimizado para conversão em linguagem assembly. Há um pequeno "bug": se o particionamento não contém nenhum
1
número no final, o último loop encontran = 0
e gera um1
elemento desnecessário . No entanto, não dói, porque o código de impressão rastreia a soma do número e não imprime esse número estranho.Quando convertido em assembly embutido, esse código se parece com o seguinte:
Algumas coisas divertidas a serem observadas:
rdrand
instrução)ah
, como , o que me dá multiplicação automática por 256. Para tirar vantagem disso, sacrifiquei o suporten = 65
. Espero poder me desculpar por esse pecado ...A alocação de espaço na pilha é realizada subtraindo 0x4100 do registro do ponteiro da pilha
esp
. Esta é uma instrução de 6 bytes! Ao adicionar esse número de volta, consegui fazê-lo em 5 bytes:Ao depurar essa função no MS Visual Studio, descobri que ela falha quando grava dados no espaço alocado na pilha! Após algumas pesquisas, descobri algum tipo de proteção contra sobrecarga de pilha: o sistema operacional parece alocar apenas um intervalo muito limitado de endereços virtuais para pilha; se uma função acessa um endereço muito distante, o SO assume que é uma saturação e mata o programa. No entanto, se uma função tiver muitas variáveis locais, o SO fará alguma "mágica" extra para fazê-la funcionar. Então, eu tenho que chamar uma função vazia que tem uma grande matriz alocada na pilha. Depois que essa função retorna, páginas adicionais da VM da pilha são alocadas e podem ser usadas.
fonte