Aleatoriedade arbitrária

26

A aleatoriedade é divertida. Desafios sem sentido são divertidos.

Escreva uma função que, dada a entrada inteira n, produza um conjunto (não ordenado, exclusivo) de nnúmeros inteiros exatamente aleatórios entre 1e n^2(inclusive), de modo que a soma de todos os números inteiros seja igual a n^2.

A aleatoriedade não precisa ser uniforme, desde que cada conjunto válido tenha uma chance diferente de zero.

A resposta mais curta em bytes (por cada idioma) vence.

Exemplos

Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1

Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3

Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2

Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4

Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8

Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1

Tarefa bônus: Existe uma fórmula para calcular o número de permutações válidas para um determinado n?

Skidsdev
fonte
2
relacionados , mas bastante diferente
Giuseppe
1
(p / s:. Se você tem um algoritmo rápido, mas demora mais bytes, considerar esperar até a edição velocidade (atualmente na caixa de areia) para postá-lo)
user202729
1
@EriktheOutgolfer Embora existam (muito) maneiras melhores do que gerar todos os conjuntos e escolher um aleatório, elas são muito mais difíceis de implementar e provavelmente mais. Guarde-os para a edição de velocidade.
user202729
2
O número de conjuntos é OEIS A107379 .
Nwellnhof
1
São os dois. Veja o comentário "Também o número de partições de n ^ 2 em n partes distintas".
Nwellnhof

Respostas:

9

Brachylog (v2), 15 bytes (aleatório) ou 13 bytes (todas as possibilidades)

Aleatória

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

Experimente online!

Envio de função (visto no TIO com um wrapper transformando-o em um programa completo).

Explicação

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              and it is composed entirely of
  ℕ₁                 integers ≥ 1,
       √           for which the square root of the
      +              sum of the list
        ?              is the input.
     A   ∧A      Restricting yourself to lists with that property,
           ≜₁      pick random possible values
             ᵐ       for each element in turn,
              ≠    until you find one whose elements are all distinct.

Todas as possibilidades

~lℕ₁ᵐ<₁.+√?∧≜

Experimente online!

Envio de função, que gera todas as saídas possíveis.

Explicação

~lℕ₁ᵐ<₁.+√?∧≜
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              it is composed entirely of
  ℕ₁                 integers ≥ 1,
     <₁            it is strictly increasing,
         √         and the square root of the
        +            sum of the list
          ?            is the input.
       .   ∧≜    Generate all specific lists with that property.

Estou bastante surpreso que ∧≜funcione (você normalmente teria que escrever ∧~≜para forçar a saída em vez da entrada), mas acontece que tem uma suposição de entrada = saída, portanto, não importa o caminho que você executá-lo.

Tarefa bônus

Para ter uma ideia da sequência do número de possibilidades, criei um wrapper TIO diferente que executa o programa em números inteiros sucessivos para fornecer a sequência das contagens de saída:

1,1,3,9,30,110,436,1801,7657,33401

Uma viagem ao OEIS descobre que essa já é uma sequência conhecida, A107379 , descrita praticamente como na pergunta (aparentemente, você obtém a mesma sequência se a restringir a números ímpares). A página lista várias fórmulas para a sequência (embora nenhuma seja particularmente simples; a segunda parece uma fórmula direta para o valor, mas eu não entendo a notação).

ais523
fonte
A segunda fórmula é "o coeficiente de x^(n*(n-1)/2)na expansão da série de Product_{k=1..n} 1/(1 - x^k)" (não directa em todos, infelizmente)
user202729
Colocar a restrição "todos diferentes" antes da etapa de rotulagem aleatória (por exemplo A≠≜₁ᵐ) torna o tempo de execução muito mais rápido, em média.
Fatalize
Não entendo por que você fez deste um wiki da comunidade. Essa é uma maneira arcaica de ter postagens editáveis ​​antes que fosse possível editar.
pipe
7

05AB1E , 11 bytes

nÅœʒDÙQ}sùΩ

Experimente online ou verifique todos os casos de teste .

Explicação:

n             # Take the square of the (implicit) input
              #  i.e. 3 → 9
 Ŝ           # Get all integer-lists using integers in the range [1, val) that sum to val
              #  i.e. 9 → [[1,1,1,1,1,1,1,1,1],...,[1,3,5],...,[9]]
   ʒ   }      # Filter the list to only keep lists with unique values:
    D         # Duplicate the current value
     Ù        # Uniquify it
              #  i.e. [2,2,5] → [2,5]
      Q       # Check if it's still the same
              #  i.e. [2,2,5] and [2,5] → 0 (falsey)
        s     # Swap to take the (implicit) input again
         ù    # Only leave lists of that size
              #  i.e. [[1,2,6],[1,3,5],[1,8],[2,3,4],[2,7],[3,6],[4,5],[9]] and 3
              #   → [[1,2,6],[1,3,5],[2,3,4]]
          Ω   # Pick a random list from the list of lists (and output implicitly)
Kevin Cruijssen
fonte
5

Python (2 ou 3), 85 bytes

def f(n):r=sample(range(1,n*n+1),n);return(n*n==sum(r))*r or f(n)
from random import*

Experimente online!

Jonathan Allan
fonte
5

R , 68, 75 48 bytes (aleatório) e 70 bytes (determinístico)

@ Método de amostragem por rejeição de Giuseppe:

function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

Experimente online!

Original de golfe:

function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

Experimente online!

O *!!1:2negócio é evitar a maneira estranha de sampleagir quando o primeiro argumento tiver comprimento 1.

ngm
fonte
@Giuseppe "fixed" :-)
ngm
muito agradável. usar pdiretamente como um índice em vez de calculá-lo e reutilizá-lo deve economizar alguns bytes.
21818 Giuseppe #:
1
Eu tenho function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}para 48, bem ...
Giuseppe
1
@ J.Doe para evitar o problema ao chamar algo parecido com o sample(2,1)que acontece n=2. Portanto, repapenas garante que isso nunca acontecerá. Pode haver uma maneira melhor, mas isso foi rápido e eu estava com raiva sample.
ngm
1
Você pode salvar um byte com x*!!1:2over rep(x,2)se sua meta questão receber um não.
J.Doe
4

Geléia , 9 bytes

²œcS=¥Ƈ²X

Experimente online!

Gere todas as n combinações da lista [1..n²], filtre para manter as que possuem a soma n² e escolha uma aleatória.

user202729
fonte
4

Java 10, 250 242 222 bytes

import java.util.*;n->{for(;;){int i=n+1,r[]=new int[i],d[]=new int[n];for(r[n<2?0:1]=n*n;i-->2;r[i]=(int)(Math.random()*n*n));var S=new HashSet();for(Arrays.sort(r),i=n;i-->0;)S.add(d[i]=r[i+1]-r[i]);if(!S.contains(0)&S.size()==n)return S;}}

-20 bytes graças a @nwellnhof .

Cuidado, o Java está chegando .. É 'apenas' cinco vezes, enquanto as outras quatro respostas combinadas, então não é tão ruim, eu acho .. rofl.
Ele n=1atravessan=25 (combinado) em menos de 2 segundos, então eu provavelmente vou postar uma versão modificada para a versão de velocidade deste desafio (que é actualmente ainda no Sandbox) também.

Experimente online.

Explicação:

No pseudo-código, fazemos o seguinte:

1) Gerar uma matriz de tamanho n+1contendo: 0, nquadrado, e n-1quantidade de números inteiros aleatórios no intervalo [0, n squared)
2) Separar esta matriz
3) Criar uma segunda gama de tamanho ncontendo as diferenças para a frente de pares
Estes três primeiros passos nos dará uma matriz contendo naleatório números inteiros (no intervalo [0, n squared)que soma ao nquadrado.
4a) Se nem todos os valores aleatórios forem únicos, ou se algum deles for 0: tente novamente a partir da etapa 1
4b) Outro: retorne essa matriz de diferenças como resultado

Quanto ao código real:

import java.util.*;      // Required import for HashSet and Arrays
n->{                     // Method with int parameter and Set return-type
  for(;;){               //  Loop indefinitely
    int i=n+1,           //   Set `i` to `n+1`
        r[]=new int[i];  //   Create an array of size `n+1`
    var S=new HashSet(); //   Result-set, starting empty
    for(r[n<2?           //   If `n` is 1:
           0             //    Set the first item in the first array to:
          :              //   Else:
           1]            //    Set the second item in the first array to:
             =n*n;       //   `n` squared
        i-->2;)          //   Loop `i` in the range [`n`, 2]:
      r[i]=              //    Set the `i`'th value in the first array to:
           (int)(Math.random()*n*n); 
                         //     A random value in the range [0, `n` squared)
    for(Arrays.sort(r),  //   Sort the first array
        i=n;i-->0;)      //   Loop `i` in the range (`n`, 0]:
      S.add(             //    Add to the Set:
        r[i+1]-r[i]);    //     The `i+1`'th and `i`'th difference of the first array
    if(!S.contains(0)    //   If the Set does not contain a 0
       &S.size()==n)     //   and its size is equal to `n`:
      return S;}}        //    Return this Set as the result
                         //   (Implicit else: continue the infinite loop)
Kevin Cruijssen
fonte
1
n=25em menos de 2 segundos é impressionante! Vou ter que ler a explicação e ver como isso acontece. Ainda é um método de força bruta?
Skidsdev
É uniforme? -
user202729
@ user202729 Embora eu não tenha certeza de como provar isso, acho que é. O Java embutido é uniforme, e usa isso para obter valores aleatórios no intervalo [0, n squared)primeiro e depois calcula as diferenças entre esses valores aleatórios classificados (incluindo inicial 0e final n squared. Por isso, tenho certeza de que essas diferenças também são uniformes. , eu não sei como provar isso Uniformidade na aleatoriedade não é realmente a minha experiência tbh..
Kevin Cruijssen
3
Você nunca lê da matriz de diferenças dou estou perdendo alguma coisa?
Nwellnhof 20/11
1
Estou meio que satisfeito com minha solução de 127 bytes : D
Olivier Grégoire
4

Perl 6 , 41 bytes

{first *.sum==$_²,(1..$_²).pick($_)xx*}

Experimente online!

  • (1 .. $_²) é o intervalo de números de 1 ao quadrado do número de entrada
  • .pick($_) escolhe aleatoriamente um subconjunto distinto desse intervalo
  • xx * replica a expressão anterior infinitamente
  • first *.sum == $_² seleciona o primeiro desses conjuntos de números que soma ao quadrado do número de entrada
Sean
fonte
40 bytes
Jo King
2

Pitão, 13 12 bytes

Ofq*QQsT.cS*

Experimente online aqui . Observe que o intérprete online executa um MemoryError para entradas maiores que 5.

Ofq*QQsT.cS*QQQ   Implicit: Q=eval(input())
                 Trailing QQQ inferred
          S*QQQ   [1-Q*Q]
        .c    Q   All combinations of the above of length Q, without repeats
 f                Keep elements of the above, as T, where the following is truthy:
      sT            Is the sum of T...
  q                 ... equal to...
   *QQ              ... Q*Q?
O                 Choose a random element of those remaining sets, implicit print

Editar: salvou um byte usando uma abordagem alternativa. Versão anterior: Of&qQlT{IT./*

Sok
fonte
2

Python 3 , 136 134 127 121 114 bytes

from random import*
def f(n):
	s={randint(1,n*n)for _ in range(n)}
	return len(s)==n and sum(s)==n*n and s or f(n)

Experimente online!

Um comentarista me corrigiu, e isso agora atinge a profundidade máxima da recursão em f (5) em vez de f (1). Muito mais perto de ser uma resposta real e competitiva.

Eu já vi fazer (5) uma vez e estou tentando implementar isso com o shuffle.

Tentei criar algumas expressões lambda para s=..., mas isso não ajudou em bytes. Talvez alguém possa fazer algo com isso: s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)

Obrigado a Kevin por remover outros 7 bytes.

Gigaflop
fonte
1
Portanto, isso usa recursão para "regenerar" o conjunto se o gerado for inválido? Definitivamente, algo está errado com o seu código, se estiver atingindo a profundidade de recursão em f(1), a única matriz possível que deve ser gerável n=1é. [1]Também há muito espaço em branco estranho a ser removido aqui. Recordar que este é um desafio code-golfe, de modo que o objetivo é conseguir o menor bytecount
Skidsdev
1
range(1,n)-> range(n)Eu acredito que deveria resolver o bug.
Jonathan Allan
1
Isso deve corrigir seu erro e também remove espaços em branco estranhos. Imagino que há muito mais espaço para jogar golfe também
Skidsdev
1
Embora a recursão piore levemente de 5 para 4, você pode combinar suas duas instruções de retorno como esta: return len(s)==n and sum(s)==n*n and s or f(n)( Experimente on-line 114 bytes ).
Kevin Cruijssen
1
Você pode ter tudo em uma linha. 111 bytes
Jo rei
2

APL (Dyalog Unicode) , SBCS de 20 bytes

Prefixo anônimo lambda.

{s=+/c←⍵?s←⍵*2:c⋄∇⍵}

Experimente online!

{...}  "dfn"; é argumento

⍵*2 esquadrar o argumento

s← atribuir a s(para s quare)

⍵? encontre níndices aleatórios de 1…s sem substituição

c← atribuir a c(para c andidate)

+/ somar eles

s= comparado a s

: se igual

  c devolver o candidato

 outro

  ∇⍵ recuar sobre o argumento

Adão
fonte
você viu os meus 18 bytes e os de H.PWiz ?
NGN
@ngn Não, claramente não, mas verifiquei se nenhuma solução de APL foi publicada antes de ser publicada. Por que nenhum de vocês‽?
Adám
Bem, uma vez eu golfed-lo e mostraram-no para o pomar, não há quase nenhum incentivo para pós :)
NGN
@ngn Para você, não, mas para mim existe.
Adám
1
certamente, e eu acho que você está fazendo um ótimo trabalho popularizando a aplicação aqui. eu estava apenas ter certeza que você sabe soluções mais curtos foram encontrados e provavelmente é melhor para explicar um deles (ou uma variação) em vez
NGN
2

APL (Dyalog Classic) , 18 bytes

(≢?≢×≢)⍣(0=+.-∘≢)⍳

Experimente online!

usa ⎕io←1

gera os números 1 2 ... n

(... )⍣(... )continue aplicando a função à esquerda até que a função à direita retorne verdadeira

comprimento, ie n

≢?≢×≢escolha nnúmeros inteiros aleatoriamente distintos entre 1 e n2

+.-∘≢ subtrair o comprimento de cada número e soma

0= se a soma for 0, pare de repetir, caso contrário, tente novamente

ngn
fonte
1

MATL , 18 13 bytes

`xGU:GZrtsGU-

Experimente online!

`	# do..while:
x	# delete from stack. This implicitly reads input the first time
	# and removes it. It also deletes the previous invalid answer.
GU:	# paste input and push [1...n^2]
GZr	# select a single combination of n elements from [1..n^2]
tsGU-	# is the sum equal to N^2? if yes, terminate and print results, else goto top
Giuseppe
fonte
Eu não tentaria isso em R - caracteres aleatórios quase nunca produzem um programa válido.
ngm
@ngm hahaha Suponho que uma explicação esteja em ordem.
Giuseppe
1

Japonês, 12 bytes

²õ àU ö@²¥Xx

Tente

                 :Implicit input of integer U
²                :U squared
 õ               :Range [1,U²]
   àU            :Combinations of length U
      ö@         :Return a random element that returns true when passed through the following function as X
        ²        :  U squared
         ¥       :  Equals
          Xx     :  X reduced by addition
Shaggy
fonte
De acordo com um comentário feito pelo OP, a ordem dos elementos na saída é irrelevante, portanto àdeve ser razoável.
Kamil Drakari #
Obrigado, @KamilDrakari. Atualizada.
Shaggy
1

Java (JDK) , 127 bytes

n->{for(int s;;){var r=new java.util.TreeSet();for(s=n*n;s>0;)r.add(s-(s-=Math.random()*n*n+1));if(r.size()==n&s==0)return r;}}

Experimente online!

Loop infinito até que um conjunto com os critérios corresponda.

Espero que você tenha tempo, porque é muito sloooooow! Não pode nem chegar a 10 sem tempo limite.

Olivier Grégoire
fonte
Você pode jogar 3 bytes de golfe alterando if(r.size()==n&s==0)para if(r.size()+s==n).
Kevin Cruijssen
@KevinCruijssen Eu pensei sobre isso também, mas não, não posso, porque s pode ser -1 en pode ser tamanho () - 1.
Olivier Grégoire
Ah, espere, você continua adicionando itens ao conjunto desde que s>0, para que o tamanho possa ser maior que n. Ok, nesse caso, de fato não funciona. né uma constante, mas infelizmente ambas se r.size()são variáveis ​​que podem estar abaixo ou acima 0e nrespectivamente.
23718 Kevin Kevin Kurtzssen
1

Lote, 182 145 bytes

@set/an=%1,r=n*n,l=r+1
@for /l %%i in (%1,-1,1)do @set/at=n*(n-=1)/2,m=(r+t+n)/-~n,r-=l=m+%random%%%((l-=x=r+1-t)*(l^>^>31)+x-m)&call echo %%l%%

Explicação: Calcula a seleção mínima e máxima permitida, considerando que os números devem ser selecionados em ordem decrescente e escolhe um valor aleatório dentro do intervalo. Exemplo para uma entrada de 4:

  • Começamos com 16 à esquerda. Não podemos escolher 11 ou mais porque as 3 escolhas restantes devem adicionar pelo menos 6. Também precisamos escolher pelo menos 6, porque se escolhermos apenas 5, as 3 escolhas restantes poderão adicionar apenas 9, o que não é suficiente para 16. Escolhemos um valor aleatório de 6 a 10, digamos 6.
  • Temos 10 restantes. Não podemos escolher 8 ou mais, porque as 2 escolhas restantes devem adicionar pelo menos 3. Como acontece, não podemos escolher 6 ou mais porque escolhemos 6 da última vez. Também precisamos escolher pelo menos 5, porque se escolhermos apenas 4, as 2 escolhas restantes só podem adicionar a 5, para um total geral de 15. Nós escolhemos um valor aleatório de 5 a 5, digamos 5 (!).
  • Temos 5 restantes. Não podemos escolher 5 ou mais porque a seleção restante deve adicionar pelo menos 1 e também porque escolhemos 5 da última vez. Também precisamos escolher pelo menos 3, porque se escolhermos apenas 2, a escolha restante poderá ser apenas 1, para um total geral de 14. Escolhemos um valor aleatório de 3 a 4, digamos 4.
  • Temos 1 restantes. Como se vê, o algoritmo escolhe um intervalo de 1 a 1, e escolhemos 1 como o número final.
Neil
fonte
1

JavaScript, 647 291 261 260 259 251 239 bytes

Obrigado a @Veskah por -10 bytes na versão original e "Ah, sim, você está produzindo todos os conjuntos, enquanto o desafio pede que um aleatório seja retornado"

(n,g=m=n**2,r=[...Array(g||1)].map(_=>m--).sort(_=>.5-Math.random()).slice(-n),c=_=>eval(r.join`+`),i=_=>r.includes(_))=>[...{*0(){while(g>1&&c()!=g){for(z of r){y=c();r[m++%n]=y>g&&!(!(z-1)||i(z-1))?z-1:y<g&&!i(z+1)?z+1:z}}yield*r}}[0]()]

Experimente online!

Crie uma matriz de n^2índices baseados em 1, classifique a matriz aleatoriamente, corte nelementos da matriz. Enquanto a soma dos elementos aleatórios não é igual à n^2matriz de loop de elementos aleatórios; se a soma dos elementos da matriz for maior que n^2e o elemento atual -1não for igual a zero ou o elemento atual -1não estiver na matriz atual, subtraia 1; se a soma da matriz for menor que n^2e o elemento atual +1não estiver na matriz, adicione 1ao elemento Se a soma da matriz for igual ao n^2loop de interrupção, imprima a matriz.

guest271314
fonte
1
637 bytes , puxando z.join em uma variável, ek++
Veskah
@Veskah Os dois whileloops provavelmente também podem ser reduzidos ao corpo de uma única função que aceita parâmetros; e poderia substituir operadores condicionais (ternários) pelas if..elsedeclarações; entre outras partes do código que provavelmente poderiam ser ajustadas para o golfe; ieg, removendo letinstruções.
guest271314
@Veskah 601 bytes sem substituir o ternário porif..else
guest271314
1
Ah, sim, você está produzindo todos os conjuntos, enquanto o desafio pede que um aleatório seja retornado (veja os comentários do OP para obter mais detalhes)
Veskah
@Veskah Deve ter interpretado mal o desafio e os exemplos, ou estava muito concentrado em resolver esta parte da pergunta " Tarefa bônus: existe uma fórmula para calcular o número de permutações válidas para um dado n?" . testando resultado esperado se o algoritmo consistentemente devolvido para n^2matrizes de saída gerados em uma única chamada para a função, e considerando simultaneamente as semelhanças com esta questão N N-dimensional ^ N matriz preenchido com N .
guest271314
0

Japonês , 20 bytes

²õ ö¬oU íUõ+)Õæ@²¥Xx

Experimente online!

Extremamente tira proveito da aleatoriedade "Não uniforme", quase sempre gera os primeiros nnúmeros ímpares, que somam n^2. Em teoria, ele pode gerar qualquer outro conjunto válido, embora eu tenha sido capaz de confirmar isso apenas para pequenos n.

Explicação:

²õ                      :Generate the range [1...n^2]
   ö¬                   :Order it randomly
     oU                 :Get the last n items
        í   )Õ          :Put it in an array with...
         Uõ+            : The first n odd numbers
              æ_        :Get the first one where...
                  Xx    : The sum
                ²¥      : equals n^2
Kamil Drakari
fonte
0

Ruby , 46 bytes

->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}

Experimente online!

GB
fonte
0

C (gcc) , 128 125 bytes

p(_){printf("%d ",_);}f(n,x,y,i){x=n*n;y=1;for(i=0;++i<n;p(y),x-=y++)while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(x);}

Experimente online!

-3 bytes graças a ceilingcat

NOTA: A probabilidade está muito longe de ser uniforme. Veja a explicação do que quero dizer e um meio melhor de testar se ele funciona (tornando a distribuição mais próxima do uniforme [mas ainda muito longe disso]).

Quão?

A idéia básica é escolher apenas números crescentes para não se preocupar com duplicatas. Sempre que escolhemos um número, temos uma chance diferente de zero de ignorá-lo, se permitido.

Para decidir se podemos pular um número, precisamos saber xo total restante a ser atingido, ko número de elementos que ainda precisamos usar e yo valor atual do candidato. O menor número possível que ainda poderíamos escolher consistiria em

y+(y+1)+(y+2)+...
adicionado ao valor atual. Em particular, exigimos que a expressão acima seja menor que x. A fórmula será
k(k+1)2+k(y+1)+y<x
Infelizmente, temos que ter um pouco de cuidado em reorganizar essa fórmula devido ao truncamento inteiro em C, por isso não consegui realmente encontrar uma maneira de jogar golfe.

No entanto, a lógica é ter a chance de descartar qualquer yque satisfaça a equação acima.

O código

p(_){printf("%d ",_);}  // Define print(int)
f(n,x,y,i){             // Define f(n,...) as the function we want
    x=n*n;              // Set x to n^2
    y=1;                // Set y to 1
    for(i=0;++i<n;){    // n-1 times do...
        while(rand()&&  // While rand() is non-zero [very very likely] AND
            (n-i)*      // (n-i) is the 'k' in the formula
            (n-i+1)/2+  // This first half takes care of the increment
            (n-i)*(y+1) // This second half takes care of the y+1 starting point
            +y<x)       // The +y takes care of the current value of y
        y++;            // If rand() returned non-zero and we can skip y, do so
    p(y);               // Print y
    x-=y++;             // Subtract y from the total and increment it
    }p(x);}             // Print what's left over.

O truque que mencionei para testar melhor o código envolve a substituição rand()&&por, rand()%2&&para que haja uma chance de 50 a 50 de que qualquer y seja ignorado, em vez de 1 em RAND_MAXchance de que qualquer y seja usado.

LambdaBeta
fonte
Eu adoraria se alguém verificasse minha matemática em busca de consistência. Também me pergunto se esse tipo de solução poderia simplificar o desafio uniforme da velocidade aleatória. A fórmula coloca um limite superior e inferior na resposta. Um número aleatório uniforme nesse intervalo resulta em resultados aleatórios uniformes? Não vejo por que não - mas não faço muita combinatória há algum tempo.
LambdaBeta
Sugerir em p(y),x-=y++)while(rand()&&(i-n)*((~n+i)/2+~y)+y<x)y++;vez de){while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(y);x-=y++;}
ceilingcat
@ceilingcat Eu amo essas pequenas melhorias que você encontra. Eu sempre ficar tão focado no algoritmo geral I esqueça de otimizar para a implementação (eu basicamente ir piloto automático modo de golfe uma vez que tenho uma fonte não-golfed que as obras - para que eu perca um monte de poupança)
LambdaBeta
Ei, não é só você quem tem esses golfinhos de sintaxe. Encontro poucas melhorias em muitas respostas em C / C ++ como essa (exceto na sua, o @ceilingcat geralmente as encaixa).
Zachary
Sim, notei que vocês dois são provavelmente os putters C / C ++ mais ativos (podemos usar o put para estender a analogia do golfe até os últimos golpes? Por que não!). Sempre me impressiona que você possa entender o código golfado o suficiente para melhorá-lo.
LambdaBeta
0

Limpo , 172 bytes

import StdEnv,Math.Random,Data.List
? ::!Int->Int
?_=code{
ccall time "I:I"
}
$n=find(\s=length s==n&&sum s==n^2)(subsequences(nub(map(inc o\e=e rem n^2)(genRandInt(?0)))))

Experimente online!

Furioso
fonte
0

Python (2 ou 3), 84 bytes

from random import*;l=lambda n,s=[]:(sum(s)==n*n)*s or l(n,sample(range(1,n*n+1),n))

Experimente online!

Atinge a profundidade máxima de recursão em torno de l (5)

ArBo
fonte
0

Kotlin , 32 bytes

{(1..it*it).shuffled().take(it)}

Experimente online!

Caracol_
fonte
1
A soma precisa ser n ^ 2
12Me21 24/11
0

Mathematica 40 bytes

RandomChoice[IntegerPartitions[n^2, {n}]]
David G. Stork
fonte
1
Primeiro de tudo, é n ^ 2, não 2 ^ n. Em segundo lugar, seu programa deve ser uma função e também um jogo de golfe. Tente isso # RandomChoice@IntegerPartitions[#^2,{#}]&
J42161217 25/11
1
Além disso, o resultado deve ser (não ordenadas, único), mas esta função não tanto
J42161217
0

Wolfram Language (Mathematica) , 49 bytes

(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

Experimente online!

Versão Golfed por @ J42161217.


Wolfram Language (Mathematica) , 62 bytes

Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&

Experimente online!

Como funciona

Principalmente com base em esta questão Math.SE . Para obter partições den2 para dentro n partes distintas, obtenha partições de n2-(n2-n)/2=(n2+n)/2 em vez disso e adicione 0 0n-1para cada elemento. Como o Mathematica fornece as partições em ordem decrescente,n-10 0 é adicionado em seu lugar.


A resposta para a tarefa de bônus

Tarefa bônus: Existe uma fórmula para calcular o número de permutações válidas para um determinado n?

Sim. Definirpumart(n,k) como o número de partições de n exatamente kpeças. Em seguida, ele satisfaz a seguinte relação de recorrência:

pumart(n,k)=pumart(n-1,k-1)+pumart(n-k,k)

Você pode entendê-lo como "Se uma partição contiver 1, remova-a; caso contrário, subtraia 1 de cada termo". Mais explicações aqui na outra pergunta Math.SE . Combinado com as condições iniciaispumart(n,1)=1 e n<kpumart(n,k)=0 0, você pode computá-lo com um programa. A resposta desejada será:

pumart(n2+n2,n)

ou seja, no Mathematica:

Length@IntegerPartitions[#*(#+1)/2,{#}]&

Experimente online!

Bubbler
fonte
Este é o código golf .. 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
J42161217 25/11