Vamos imaginar que temos um conjunto finito de números inteiros positivos. Este conjunto pode ser representado como uma linha de pontos em que cada número inteiro presente no conjunto é preenchido como um scantron ou cartão perfurado . Por exemplo, o conjunto {1,3,4,6}pode ser representado como:
*.**.*
*representa um membro do nosso conjunto e .representa um número inteiro que não é um membro do conjunto.
Esses conjuntos têm "fatores". Vagamente x é um fator de y se y puder ser construído a partir de cópias de x. Mais rigorosamente, nossa definição de fator é a seguinte:
- x é um fator de y se e somente se y é a união de um número de conjuntos disjuntos , todos os quais são x com um deslocamento.
Nós chamaríamos *.*um fator de *.**.*porque é claramente composto por duas cópias de *.*pôr fim a fim.
*.**.*
------
*.*...
...*.*
Como os fatores não precisam ser completos, diríamos também que esse *.*é um fator de*.*.*.*
*.*.*.*
-------
*.*....
....*.*
Os fatores também podem se sobrepor. Isso significa *.*também é um fator de****
****
----
*.*.
.*.*
No entanto, um número não pode ser coberto por um fator mais de uma vez. Por exemplo, não*.* é um fator de .*.*.*
Aqui está um exemplo mais complicado:
*..*.**..***.*.*
Isso tem *..*.*como um fator. Você pode ver isso abaixo, onde eu alinhei as três instâncias de *..*.*.
*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*
Tarefa
Dado um conjunto por qualquer representação razoável, todos os conjuntos são fatores da entrada.
Você pode indexar por qualquer valor (ou seja, você pode selecionar um número menor que possa estar presente na entrada). Você também pode assumir que o conjunto de entrada sempre conterá o menor valor.
Esta é uma questão de código-golfe, então você deve tentar fazer isso no menor número de bytes possível.
Casos de teste
Esses casos de teste foram feitos à mão, pode haver um ou dois erros nos maiores
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
fonte
[1,3,5,7]para*.*.*.*), podemos assumir que ele está classificado?*.*.*=x+x^2+x^4, então1+x+x^2=***seria um divisor, certo?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)*é listado como um fator que representa o mesmo subconjunto de*.ou*...Respostas:
Mathematica,
7168 bytesEntrada como
{1,3,5,7}(classificada) e saída como{{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. A função lançará um monte de mensagens.Este é O (2 2 Nope ) (onde N é o comprimento da entrada e o = p = e = 1 ...). Ele gera todos os subconjuntos de subconjuntos e, em seguida, seleciona aqueles que resultam no envio de entrada quando unidos (garantindo que estamos considerando apenas partições) e onde todos os elementos são iguais se subtrairmos o menor valor de cada subconjunto.
fonte
Geléia , 12 bytes
Entrada e saída usam
1e, em0vez de*e..Experimente online!
Como funciona
fonte