Localizar fatores de subconjunto

14

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 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

*                -> *
*.*.*            -> *, *.*.*
*.*.*.*          -> *, *.*, *...*, *.*.*.*
******           -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.**  -> *, *...**.**, *.....*, *...*****.**.**
Post Rock Garf Hunter
fonte
Se considerarmos o conjunto como uma lista de números (por exemplo, [1,3,5,7]para *.*.*.*), podemos assumir que ele está classificado?
Martin Ender
1
Isso é equivalente a encontrar divisores de polinômios cujos coeficientes são restritos a 0 e 1?
xnor
1
@ xnor Não tenho certeza. Se *.*.*= x+x^2+x^4, então 1+x+x^2= ***seria um divisor, certo?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)
mbomb007
1
@ JonathanAllan Para seus exemplos, *é listado como um fator que representa o mesmo subconjunto de*. ou *...
Martin Ender
1
@ JonathanAllan Diz output todos os conjuntos, não gera todas as representações ASCII dos conjuntos válidos.
Martin Ender

Respostas:

3

Mathematica, 71 68 bytes

#&@@@Cases[(s=Subsets)@s@#,x_/;Sort[Join@@x]==#&&Equal@@(#&@@@x-x)]&

Entrada 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.

Martin Ender
fonte
2

Geléia , 12 bytes

;÷@DỊȦ
ÆDçÐf

Entrada e saída usam 1e, em 0vez de* e ..

Experimente online!

Como funciona

ÆDçÐf   Main link. Argument: n (integer with decimal digits 1 and 0)

ÆD      Compute all divisors of n.
  çÐf   Filter; call the helper link with left argument d and right argument n for
        all divisors d of n. Return the array of d's for which the helper link
        returns a truthy value.


;÷@DỊȦ  Helper link. Left argument: d. Right argument: n

 ÷@     Divide n by d.
;       Concatenate, yielding [d, n÷d].
   D    Decimal; convert both integers in the pair to base 10.
    Ị   Insignificant; map 1 and 0 to 1, all other positive integers to 0.
     Ȧ  All; return 1 iff the result contains no zeroes.
Dennis
fonte