14
Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example the set {1,3,4,6}
could be represented as:
*.**.*
*
represents a member of our set and .
represents an integer that is not a member oft he set.
These sets have "factors". Loosely x is a factor of y if y can be built out of copies of x. More rigorously our definition of factor is as follows:
- x is a factor of y if and only if y is the union of a number of disjoint sets, all of which are x with an offset.
We would call *.*
a factor of *.**.*
because it is quite clearly made up of two copies of *.*
put end to end.
*.**.*
------
*.*...
...*.*
Factors don't have to be end to end, we would also say that *.*
is a factor of *.*.*.*
*.*.*.*
-------
*.*....
....*.*
Factors can also overlap. This means *.*
is also a factor of ****
****
----
*.*.
.*.*
However a number cannot be covered by a factor more than once. For example *.*
is not a factor of *.*.*
.
Here is a more complicated example:
*..*.**..***.*.*
This has *..*.*
as a factor. You can see that below where I have lined up the three instances of *..*.*
.
*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*
Task
Given a set by any reasonable representation output all the sets that are factors of the input.
You may index by any value, (that is you may select a smallest number that can be present in the input). You may also assume that the input set will always contain that smallest value.
This is a code-golf question so you should aim to do this in as few bytes as possible.
Test Cases
These test cases were done by hand, there may be a mistake or two on the larger ones
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
If we take the set as a list of numbers (e.g.
[1,3,5,7]
for*.*.*.*
) can we assume that it's sorted? – Martin Ender – 2017-06-02T13:25:44.260@MartinEnder Yes. I forgot to add but you can also always assume it contains 1 if you wish. – Post Rock Garf Hunter – 2017-06-02T13:27:56.203
1Is this equivalent to finding divisors of polynomials whose coefficients are restricted to 0 and 1? – xnor – 2017-06-02T13:28:00.797
1@xnor I'm not sure. If
*.*.*
=x+x^2+x^4
, then1+x+x^2
=***
would be a divisor, right?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)
– mbomb007 – 2017-06-02T13:33:18.397If
*...*
is a factor of*.*.*.*
why is*.
not a factor too? (also of*.*.*
, and why is*..
not; etc?) EDIT: because they cant overflow the end? – Jonathan Allan – 2017-06-02T13:34:32.1531@JonathanAllan For your examples,
*
is listed as a factor which represents the same subset as*.
or*..
. – Martin Ender – 2017-06-02T13:35:55.623@MartinEnder It does not say that anywhere, but it makes sense (in fact it says "output all"). – Jonathan Allan – 2017-06-02T13:40:59.387
@mbomb007 Good point, the lack of negative coefficients makes a difference. – xnor – 2017-06-02T13:41:25.313
Can our input set be "0-indexed", having
0
instead of1
? – mbomb007 – 2017-06-02T13:48:13.8671@JonathanAllan It says output all sets, not output all ASCII representations of the valid sets. – Martin Ender – 2017-06-02T13:48:46.100