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
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
[1,3,5,7]
for*.*.*.*
) can we assume that it's sorted? \$\endgroup\$ – Martin Ender Jun 2 '17 at 13:25*.*.*
=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)
\$\endgroup\$ – mbomb007 Jun 2 '17 at 13:33*
is listed as a factor which represents the same subset as*.
or*..
. \$\endgroup\$ – Martin Ender Jun 2 '17 at 13:35