-5

How can I implement a function that applied to that list gives me the minimal group of elements, which if repeated n times generates that list?

e.g. 

a = [1,2,3,4,1,2,3,4,1,2,3,4]
foo(a)

returns [1,2,3,4]

a = [1,1,1,1]
foo(a)

returns [1]

a = [1,2,3,4,5,6]
foo(a)

returns [1,2,3,4,5,6]

EDIT

in other words this function needs to find the germ (see the solution below), a group of elements whose mere repetition generates the list exactly as it is.

A duplicates reduction function would not suffice because, for instance, [1,2,1,1] would become [1,2].

DaniPaniz
  • 1,058
  • 2
  • 13
  • 24
  • 2
    What should something like `foo([1,2,1])` return? – jwodder Oct 01 '14 at 21:04
  • possible duplicate of : http://stackoverflow.com/questions/7961363/python-removing-duplicates-in-lists – Beginner Oct 01 '14 at 21:05
  • @Beginner: the way I read this, it's not just the set of elements; for example, I believe that `[1, 1, 2, 1, 1, 2]` would become `[1, 1, 2]`, not `[1, 2]`. However, it would be best if the OP would clarify. – jscs Oct 01 '14 at 21:08
  • Yes it is unclear. But if `[1,2,1]` needs to be converted into `[1,1,2]`, isnt that just sorting? – Beginner Oct 01 '14 at 21:10
  • @Beginner no it's not [a duplicate](http://stackoverflow.com/questions/7961363/python-removing-duplicates-in-lists) – DaniPaniz Oct 01 '14 at 21:11
  • @jwodder [1,2,1] would just remain as it is. I want a function that finds "group duplicates". That is, minimal set of elements that, if repeated N times, give rise to the exact list provided as input. Could you please remove the "This question may already have an answer here" thing? – DaniPaniz Oct 01 '14 at 21:13
  • @Josh Caswell exactly, e.g. the function to remove duplicate in lists wouldn't work because [1,2,1,1,1,2,1,1,1,2,1,1] would be reduced to [1,2] and not to [1,2,1,1] – DaniPaniz Oct 01 '14 at 21:15
  • @jonrsharpe I modified the question, I guess it is clear enough as a good answer was provided. Let me know if you have further suggestions on how to improve it, cheers – DaniPaniz Oct 02 '14 at 11:37

3 Answers3

3

Here is a simple way:

def findGerm(x):
    for ix in xrange(1, len(x)+1):
        if x == x[:ix]*(len(x)//ix):
            return x[:ix]

Then:

>>> findGerm([1, 2, 3, 1, 2, 3])
[1, 2, 3]
>>> findGerm([1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3])
[1, 1, 2, 3]
>>> findGerm([3, 2, 1, 3, 2, 1])
[3, 2, 1]
>>> findGerm([1, 2, 1])
[1, 2, 1]

Basically it takes beginning chunks of the list and tries multiplying them out to equal the length of the original list. If the result equals the original list, then you have found the "germ". In the worst case, it goes all the way to the end of the list, at which point it trivially equals one repetition of itself.

BrenBarn
  • 242,874
  • 37
  • 412
  • 384
0

Maybe something like:

def foo(subject):
    def test_seq(pattern):
        if len(subject) % len(pattern) != 0: return False   # Quick length check

        for i in range(len(subject) / len(pattern)):
            offset = i * len(pattern)
            sublist = subject[offset:offset+len(pattern)]   # Extract sublist
            if sublist != pattern: return False

        return True                                         # All sublists == pattern

    for i in range(len(subject)):
        pattern = subject[0:(i+1)]
        if test_seq(pattern):
            return pattern

print foo([1,2,3,4,1,2,3,4,1,2,3,4])
print foo([1,1,1,1])
print foo([1,2,3,4,5,6])

foo(subject) generates candidate sequences based on the first n elements in subject where n = 1,2,3,...,len(subject).

Those candidate sequences (pattern) are then tested against the subject, as many times as necessary to fit, in test_seq().

jedwards
  • 29,432
  • 3
  • 65
  • 92
-2
from collections import OrderedDict

def foo(example_list):
    a = OrderedDict()
    for i in example_list:
        a[i] = i
    return [key for key in a.iterkeys()]

If pass [1,2,3,4,1,2,3,4] as an argument, it returns [1,2,3,4].

zamk
  • 71
  • 3
  • 14