Iyfjky

Question

Suppose we have a list of numbers, l. I need to COUNT all tuples of length 3 from l, (l_i,l_j,l_k) such that l_i evenly divides l_j, and l_j evenly divides l_k. With the stipulation that the indices i,j,k have the relationship i<j<k

I.e.;

If l=[1,2,3,4,5,6], then the tuples would be [1,2,6], [1,3,6],[1,2,4], so the COUNT would be 3.

If l=[1,1,1], then the only tuple would be [1,1,1], so the COUNT would be 1.

Here's what I've done so far, using list comprehensions:

def myCOUNT(l):
 newlist=[[x,y,z] for x in l for y in l for z in l if (z%y==0 and y%x==0 and l.index(x)<l.index(y) and l.index(y)<l.index(z))]
 return len(newlist)

>>>l=[1,2,3,4,5,6]
>>>myCOUNT(l)
3

This works, but as l gets longer (and it can be as large as 2000 elements long), the time it takes increases too much. Is there a faster/better way to do this?

Are you looking for a faster list comprehension, or the fastest solution (even if that means not using a list comprehension)? If the latter, what else have you tried? — Aug 11 at 23:29
Nested for loops will let you avoid those costly l.index calls. — Aug 11 at 23:30
You could also shortcut and not do the innermost loop for l_i and l_j that fail your criteria. — Aug 12 at 0:04
@PatrickHaugh--could you explain in a bit more detail what you mean here? Thank you! — Aug 12 at 2:09
Are the elements guaranteed to be sorted? Or is that just a coincidence in the example? — Aug 12 at 3:16

score 16 · Accepted Answer · 2018-08-12 02:47:08Z

We can count the number of triples with a given number in the middle by counting how many factors of that number are to its left, counting how many multiples of that number are to its right, and multiplying. Doing this for any given middle element is O(n) for a length-n list, and doing it for all n possible middle elements is O(n^2).

def num_triples(l):
 total = 0
 for mid_i, mid in enumerate(l):
 num_left = sum(1 for x in l[:mid_i] if mid % x == 0)
 num_right = sum(1 for x in l[mid_i+1:] if x % mid == 0)
 total += num_left * num_right
 return total

Incidentally, the code in your question doesn't actually work. It's fallen into the common newbie trap of calling index instead of using enumerate to get iteration indices. More than just being inefficient, this is actually wrong when the input has duplicate elements, causing your myCOUNT to return 0 instead of 1 on the [1, 1, 1] example input.

It makes sense that I fell into a newbie trap, since I've only been seriously learning python for less than 6 months (and I'm teaching myself). Thank you for the help! — Aug 13 at 18:10

score 4 · Answer 2 · 2018-08-12 03:27:33Z

Finding all tuples in O(n²)

You algorithm iterates over all possible combinations, which makes it O(n³).

Instead, you should precompute the division-tree of your list of numbers and recover triples from the paths down the tree.

Division tree

A division tree is a graph which nodes are numbers and children are the multiples of each number.

By example, given the list [1, 2, 3, 4], the division tree looks like this.

 1
 /|
 2 | 3
 |
 4

Computing the division tree requires to compare each number against all others, making its creation O(n²).

Here is a basic implementation of a division-tree that can be used for your problem.

class DivisionTree:
 def __init__(self, values):
 values = sorted(values)

 # For a division-tree to be connected, we need 1 to be its head
 # Thus we artificially add it and note whether it was actually in our numbers
 if 1 in values:
 self._has_one = True
 values = values[1:]
 else:
 self._has_one = False

 self._graph = 1: 

 for v in values:
 self.insert(v)

 def __iter__(self):
 """Iterate over all values of the division-tree"""
 yield from self._graph

 def insert(self, n):
 """Insert value in division tree, adding it as child of each divisor"""
 self._graph[n] = 

 for x in self:
 if n != x and n % x == 0:
 self._graph[x].append(n)

 def paths(self, depth, _from=1):
 """Return a generator of all paths of *depth* down the division-tree"""
 if _from == 1:
 for x in self._graph[_from]:
 yield from self.paths(depth , _from=x)

 if depth == 1:
 yield [_from]
 return

 if _from != 1 or self._has_one:
 for x in self._graph[_from]:
 for p in self.paths(depth - 1, _from=x):
 yield [_from, *p]

Usage

Once we built a DivisionTree, it suffices to iterate over all paths down the graph and select only those which have length 3.

Example

l = [1,2,3,4,5,6]

dt = DivisionTree(l)

for p in dt.paths(3):
 print(p)

Output

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

This solution assumes that the list of number is initially sorted, as in your example. Although, the output could be filtered with regard to the condition on indices i < j < k to provide a more general solution.

Time complexity

Generating the division-tree is O(n²).

In turn, there can be up to n! different paths, although stopping the iteration whenever we go deeper than 3 prevents traversing them all. This makes us iterate over the following paths:

the paths corresponding to three tuples, say there are m of them;

the paths corresponding to two tuples, there are O(n²) of them;

the paths corresponding to one tuples, there are O(n) of them.

Thus this overall yields an algorithm O(n² + m).

I agree that this will be faster--however, I feel like there's some sort of theorem about the count of 3-tuples that satisfy the division requirement. The actual problem doesn't ask for the 3-tuples, just how many there are total. So I'm suspicious that there's a simpler answer than generating all paths and then selecting those of length 3. But this is all great stuff--I really appreciate it! — Aug 12 at 2:08
@EmmGee I misread that you only needed to count them, then this answer is probably the best. Although, I'll leave my answer up for anyone that needs to find the tuples efficiently. — Aug 12 at 3:16
You don't seem to be accounting for the i<j<k constraint on the indices. — Aug 12 at 3:23
@user2357112 You are right it does not. I'll leave a note for now and fix that later — Aug 12 at 3:24

score 3 · Answer 3 · 2018-08-12 00:09:41Z

I suppose this solution without list comprehension will be faster (you can see analogue with list comprehension further):

a = [1, 2, 3, 4, 5, 6]

def count(a): 
 result = 0
 length = len(a)

 for i in range(length):
 for j in range(i + 1, length):
 for k in range(j + 1, length):
 if a[j] % a[i] == 0 and a[k] % a[j] == 0:
 result += 1

 return result

print(count(a))

Output:

In your solution index method is too expensive (requires O(n) operations). Also you don't need to iterate over full list for each x, y and z (x = a[i], y = a[j], z = a[k]). Notice how I use indexes in my loops for y and z because I know that a.index(x) < a.index(y) < a.index(z) is always satisfied.

You can write it as one liner too:

def count(a): 
 length = len(a)

 return sum(1 for i in range(length)
 for j in range(i + 1, length)
 for k in range(j + 1, length)
 if a[j] % a[i] == 0 and a[k] % a[j] == 0)

P.S.
Please, don't use l letter for variables names because it's very similar to 1:)

For some reason, this returns different values for my test cases. Also, when l is very large (i.e.; 2000 numbers in length), it takes too long... — Aug 12 at 0:01
If we're concerned with speed over readability, lookups a[i] should be faster than slices a[j+1:], especially for very large inputs — Aug 12 at 0:03
@EmmGee This is because solution is O(n^3). I'm sure that you can't improve this asymptotic. Maybe you should try to rewrite my solution in CPython or just in C/C++. It will be reasonably faster. — Aug 12 at 0:20
@LevZakharov I appreciate your solutions! Unfortunately, they all are seeming to take too long...I think there's probably some number-theory based solution having to do with the number of divisors of each element in l, so maybe I'll poke around the mathematicians and get back to this later. — Aug 12 at 0:46

score 1 · Answer 4 · 2018-08-13 08:18:47Z

There is a way to do this with itertools combinations:

from itertools import combinations 
l=[1,2,3,4,5,6] 

>>> [(x,y,z) for x,y,z in combinations(l,3) if z%y==0 and y%x==0]
[(1, 2, 4), (1, 2, 6), (1, 3, 6)]

Since combinations generates the tuples in list order, you do not then need to check the index of z.

Then your myCOUNT function becomes:

def cnt(li):
 return sum(1 for x,y,z in combinations(li,3) if z%y==0 and y%x==0)

>>> cnt([1,1,1])
1
>>> cnt([1,2,3,4,5,6])
3

This is a known problem.

Here are some timing for the solutions here:

from itertools import combinations 

class DivisionTree:
 def __init__(self, values): 
 # For a division-tree to be connected, we need 1 to be its head
 # Thus we artificially add it and note whether it was actually in our numbers
 if 1 in values:
 self._has_one = True
 values = values[1:]
 else:
 self._has_one = False

 self._graph = 1: 

 for v in values:
 self.insert(v)

 def __iter__(self):
 """Iterate over all values of the division-tree"""
 yield from self._graph

 def insert(self, n):
 """Insert value in division tree, adding it as child of each divisor"""
 self._graph[n] = 

 for x in self:
 if n != x and n % x == 0:
 self._graph[x].append(n)

 def paths(self, depth, _from=1):
 """Return a generator of all paths of *depth* down the division-tree"""
 if _from == 1:
 for x in self._graph[_from]:
 yield from self.paths(depth , _from=x)

 if depth == 1:
 yield [_from]
 return

 if _from != 1 or self._has_one:
 for x in self._graph[_from]:
 for p in self.paths(depth - 1, _from=x):
 yield [_from, *p]


def f1(li):
 return sum(1 for x,y,z in combinations(li,3) if z%y==0 and y%x==0)

def f2(l):
 newlist=[[x,y,z] for x in l for y in l for z in l if (z%y==0 and y%x==0 and l.index(x)<l.index(y) and l.index(y)<l.index(z))]
 return len(newlist)

def f3(a): 
 result = 0
 length = len(a)

 for i in range(length):
 for j in range(i + 1, length):
 for k in range(j + 1, length):
 if a[j] % a[i] == 0 and a[k] % a[j] == 0:
 result += 1

 return result

def f4(l):
 dt = DivisionTree(l)
 return sum(1 for _ in dt.paths(3)) 

def f5(l):
 total = 0
 for mid_i, mid in enumerate(l):
 num_left = sum(1 for x in l[:mid_i] if mid % x == 0)
 num_right = sum(1 for x in l[mid_i+1:] if x % mid == 0)
 total += num_left * num_right
 return total 


if __name__=='__main__':
 import timeit
 tl=list(range(3,155))
 funcs=(f1,f2,f3,f4,f5)
 td=f.__name__:f(tl) for f in funcs
 print(td)
 for case, x in (('small',50),('medium',500),('large',5000)):
 li=list(range(2,x))
 print(': elements'.format(case,x))
 for f in funcs:
 print(" :^10s:.4f secs".format(f.__name__, timeit.timeit("f(li)", setup="from __main__ import f, li", number=1)))

And the results:

'f1': 463, 'f2': 463, 'f3': 463, 'f4': 463, 'f5': 463
small: 50 elements
 f1 0.0010 secs
 f2 0.0056 secs
 f3 0.0018 secs
 f4 0.0003 secs
 f5 0.0002 secs
medium: 500 elements
 f1 1.1702 secs
 f2 5.3396 secs
 f3 1.8519 secs
 f4 0.0156 secs
 f5 0.0110 secs
large: 5000 elements
 f1 1527.4956 secs
 f2 6245.9930 secs
 f3 2074.2257 secs
 f4 1.3492 secs
 f5 1.2993 secs

You can see that f1,f2,f3 are clearly O(n^3) or worse and f4,f5 are O(n^2). f2 took more than 90 minutes for what f4 and f5 did in 1.3 seconds.

This also works, but again, takes too long. There must be a solution beyond brute forcing it... — Aug 12 at 1:49

score 0 · Answer 5 · 2018-08-13 17:33:15Z

Solution in O(M*log(M)) for a sorted list containing positive numbers

As user2357112 has answered, we can count the number of triplets in O(n^2) by calculating for every number the number of its factors and multiples. However, if instead of comparing every pair we go over its multiples smaller than the largest number and check whether they are in the list, we can change the efficiency to O(N+M*log(N)), when M is the largest number in the list.

Code:

def countTriples(myList):
 counts = #Contains the number of appearances of every number.
 factors = #Contains the number of factors of every number.
 multiples = #Contains the number of multiples of every number.

 for i in myList: #Initializing the dictionaries.
 counts[i] = 0
 factors[i] = 0
 multiples[i] = 0

 maxNum = max(myList) #The maximum number in the list.

 #First, we count the number of appearances of every number.
 for i in myList:
 counts[i] += 1

 #Then, for every number in the list, we check whether its multiples are in the list.
 for i in counts:
 for j in range(2*i, maxNum+1, i):
 if(counts.has_key(j)):
 factors[j] += counts[i]
 multiples[i] += counts[j]

 #Finally, we count the number of triples.
 ans = 0
 for i in counts:
 ans += counts[i]*factors[i]*multiples[i] #Counting triplets with three numbers.
 ans += counts[i]*(counts[i]-1)*factors[i]/2 #Counting triplets with two larger and one smaller number.
 ans += counts[i]*(counts[i]-1)*multiples[i]/2 #Counting triplets with two smaller numbers and one larger number.
 ans += counts[i]*(counts[i]-1)*(counts[i]-2)/6 #Counting triplets with three copies of the same number.

 return ans

While this solution will work quickly for lists containing many small numbers, it will not work for lists containing large numbers:

countTriples(list(range(1,1000000)) #Took 80 seconds on my computer
countTriples([1,2,1000000000000]) #Will take a very long time

Fast solution with unknown efficiency for unsorted lists

Another method to count the number of multiples and factors of every number in the list would be to use a binary tree data structure, with leaves corresponding to numbers. The data structure supports three operations:

1) Add a number to every position which is a multiple of a number.

2) Add a number to every position which is specified in a set.

3) Get the value of a position.

We use lazy propagation, and propagate the updates from the root to lower nodes only during queries.

To find the number of factors of every item in the list, we iterate over the list, query the number of factors of the current item from the data structure, and add 1 to every position which is a multiple of the item.

To find the number of multiples of every item, we first find for every item in the list all its factors using the algorithm described in the previous solution.

We then iterate over the list in the reverse order. For every item, we query the number of its multiples from the data structure, and add 1 to its factors in the data structure.

Finally, for every item, we add the multiplication of its factors and multiples to the answer.

Code:

'''A tree that supports two operations:
 addOrder(num) - If given a number, adds 1 to all the values which are multiples of the given number. If given a tuple, adds 1 to all the values in the tuple.
 getValue(num) - returns the value of the number.
 Uses lazy evaluation to speed up the algorithm.
'''
class fen:
 '''Initiates the tree from either a list, or a segment of the list designated by s and e'''
 def __init__(this, l, s = 0, e = -1):
 if(e == -1): e = len(l)-1
 this.x1 = l[s]
 this.x2 = l[e]

 this.val = 0
 this.orders = 

 if(s != e):
 this.s1 = fen(l, s, (s+e)/2)
 this.s2 = fen(l, (s+e)/2+1, e)
 else:
 this.s1 = None
 this.s2 = None

 '''Testing if a multiple of the number appears in the range of this node.'''
 def _numGood(this, num):
 if(this.x2-this.x1+1 >= num): return True
 m1 = this.x1%num
 m2 = this.x2%num
 return m1 == 0 or m1 > m2

 '''Testing if a member of the group appears in the range of this node.'''
 def _groupGood(this, group):
 low = 0
 high = len(group)
 if(this.x1 <= group[0] <= this.x2): return True
 while(low != high-1):
 mid = (low+high)/2;
 if(group[mid] < this.x1): low = mid
 elif(group[mid] > this.x2): high = mid
 else: return True
 return False

 def _isGood(this, val):
 if(type(val) == tuple):
 return this._groupGood(val)
 return this._numGood(val)

 '''Adds an order to this node.'''
 def addOrder(this, num, count = 1):
 if(not this._isGood(num)): return
 if(this.x1 == this.x2): this.val += count
 else :this.orders[num] = this.orders.get(num, 0)+count

 '''Pushes the orders to lower nodes.''' 
 def _pushOrders(this):
 if(this.x1 == this.x2): return
 for i in this.orders:
 this.s1.addOrder(i, this.orders[i])
 this.s2.addOrder(i, this.orders[i])
 this.orders = 

 def getValue(this, num):
 this._pushOrders()
 if(num < this.x1 or num > this.x2):
 return 0
 if(this.x1 == this.x2):
 return this.val
 return this.s1.getValue(num)+this.s2.getValue(num)

def countTriples2(myList):
 factors = [0 for i in myList]
 multiples = [0 for i in myList]

 numSet = set((abs(i) for i in myList))
 sortedList = sorted(list(numSet))

 #Calculating factors.
 tree = fen(sortedList)
 for i in range(len(myList)):
 factors[i] = tree.getValue(abs(myList[i]))
 tree.addOrder(abs(myList[i]))

 #Calculating the divisors of every number in the group.
 mxNum = max(numSet)
 divisors = i: for i in numSet

 for i in sortedList:
 for j in range(i, mxNum+1, i):
 if(j in numSet):
 divisors[j].append(i)
 divisors = i:tuple(divisors[i]) for i in divisors
 #Calculating the number of multiples to the right of every number.
 tree = fen(sortedList)
 for i in range(len(myList)-1, -1, -1):
 multiples[i] = tree.getValue(abs(myList[i]))
 tree.addOrder(divisors[abs(myList[i])])

 ans = 0
 for i in range(len(myList)):
 ans += factors[i]*multiples[i]

 return ans

This solution worked for a list containing the numbers 1..10000 in six seconds on my computer, and for a list containing the numbers 1..100000 in 87 seconds.

You seem to have forgotten to account for triples involving two or three copies of the same number. — Aug 12 at 17:54
Also, if you want to handle negatives, it's not enough to just do i = -i. You also need to account for negative multiples of each number, and assuming the list is sorted no longer guarantees that divisors are on the left and multiples are on the right. — Aug 12 at 17:59
Thank you for pointing out these mistakes. They are fixed now. — Aug 12 at 23:55

score 16 · Accepted Answer · 2018-08-12 02:47:08Z

We can count the number of triples with a given number in the middle by counting how many factors of that number are to its left, counting how many multiples of that number are to its right, and multiplying. Doing this for any given middle element is O(n) for a length-n list, and doing it for all n possible middle elements is O(n^2).

def num_triples(l):
 total = 0
 for mid_i, mid in enumerate(l):
 num_left = sum(1 for x in l[:mid_i] if mid % x == 0)
 num_right = sum(1 for x in l[mid_i+1:] if x % mid == 0)
 total += num_left * num_right
 return total

Incidentally, the code in your question doesn't actually work. It's fallen into the common newbie trap of calling index instead of using enumerate to get iteration indices. More than just being inefficient, this is actually wrong when the input has duplicate elements, causing your myCOUNT to return 0 instead of 1 on the [1, 1, 1] example input.

It makes sense that I fell into a newbie trap, since I've only been seriously learning python for less than 6 months (and I'm teaching myself). Thank you for the help! — Aug 13 at 18:10

score 4 · Answer 7 · 2018-08-12 03:27:33Z

Finding all tuples in O(n²)

You algorithm iterates over all possible combinations, which makes it O(n³).

Instead, you should precompute the division-tree of your list of numbers and recover triples from the paths down the tree.

Division tree

A division tree is a graph which nodes are numbers and children are the multiples of each number.

By example, given the list [1, 2, 3, 4], the division tree looks like this.

 1
 /|
 2 | 3
 |
 4

Computing the division tree requires to compare each number against all others, making its creation O(n²).

Here is a basic implementation of a division-tree that can be used for your problem.

class DivisionTree:
 def __init__(self, values):
 values = sorted(values)

 # For a division-tree to be connected, we need 1 to be its head
 # Thus we artificially add it and note whether it was actually in our numbers
 if 1 in values:
 self._has_one = True
 values = values[1:]
 else:
 self._has_one = False

 self._graph = 1: 

 for v in values:
 self.insert(v)

 def __iter__(self):
 """Iterate over all values of the division-tree"""
 yield from self._graph

 def insert(self, n):
 """Insert value in division tree, adding it as child of each divisor"""
 self._graph[n] = 

 for x in self:
 if n != x and n % x == 0:
 self._graph[x].append(n)

 def paths(self, depth, _from=1):
 """Return a generator of all paths of *depth* down the division-tree"""
 if _from == 1:
 for x in self._graph[_from]:
 yield from self.paths(depth , _from=x)

 if depth == 1:
 yield [_from]
 return

 if _from != 1 or self._has_one:
 for x in self._graph[_from]:
 for p in self.paths(depth - 1, _from=x):
 yield [_from, *p]

Usage

Once we built a DivisionTree, it suffices to iterate over all paths down the graph and select only those which have length 3.

Example

l = [1,2,3,4,5,6]

dt = DivisionTree(l)

for p in dt.paths(3):
 print(p)

Output

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

This solution assumes that the list of number is initially sorted, as in your example. Although, the output could be filtered with regard to the condition on indices i < j < k to provide a more general solution.

Time complexity

Generating the division-tree is O(n²).

In turn, there can be up to n! different paths, although stopping the iteration whenever we go deeper than 3 prevents traversing them all. This makes us iterate over the following paths:

the paths corresponding to three tuples, say there are m of them;

the paths corresponding to two tuples, there are O(n²) of them;

the paths corresponding to one tuples, there are O(n) of them.

Thus this overall yields an algorithm O(n² + m).

I agree that this will be faster--however, I feel like there's some sort of theorem about the count of 3-tuples that satisfy the division requirement. The actual problem doesn't ask for the 3-tuples, just how many there are total. So I'm suspicious that there's a simpler answer than generating all paths and then selecting those of length 3. But this is all great stuff--I really appreciate it! — Aug 12 at 2:08
@EmmGee I misread that you only needed to count them, then this answer is probably the best. Although, I'll leave my answer up for anyone that needs to find the tuples efficiently. — Aug 12 at 3:16
You don't seem to be accounting for the i<j<k constraint on the indices. — Aug 12 at 3:23
@user2357112 You are right it does not. I'll leave a note for now and fix that later — Aug 12 at 3:24

score 3 · Answer 8 · 2018-08-12 00:09:41Z

I suppose this solution without list comprehension will be faster (you can see analogue with list comprehension further):

a = [1, 2, 3, 4, 5, 6]

def count(a): 
 result = 0
 length = len(a)

 for i in range(length):
 for j in range(i + 1, length):
 for k in range(j + 1, length):
 if a[j] % a[i] == 0 and a[k] % a[j] == 0:
 result += 1

 return result

print(count(a))

Output:

In your solution index method is too expensive (requires O(n) operations). Also you don't need to iterate over full list for each x, y and z (x = a[i], y = a[j], z = a[k]). Notice how I use indexes in my loops for y and z because I know that a.index(x) < a.index(y) < a.index(z) is always satisfied.

You can write it as one liner too:

def count(a): 
 length = len(a)

 return sum(1 for i in range(length)
 for j in range(i + 1, length)
 for k in range(j + 1, length)
 if a[j] % a[i] == 0 and a[k] % a[j] == 0)

P.S.
Please, don't use l letter for variables names because it's very similar to 1:)

For some reason, this returns different values for my test cases. Also, when l is very large (i.e.; 2000 numbers in length), it takes too long... — Aug 12 at 0:01
If we're concerned with speed over readability, lookups a[i] should be faster than slices a[j+1:], especially for very large inputs — Aug 12 at 0:03
@EmmGee This is because solution is O(n^3). I'm sure that you can't improve this asymptotic. Maybe you should try to rewrite my solution in CPython or just in C/C++. It will be reasonably faster. — Aug 12 at 0:20
@LevZakharov I appreciate your solutions! Unfortunately, they all are seeming to take too long...I think there's probably some number-theory based solution having to do with the number of divisors of each element in l, so maybe I'll poke around the mathematicians and get back to this later. — Aug 12 at 0:46

score 1 · Answer 9 · 2018-08-13 08:18:47Z

There is a way to do this with itertools combinations:

from itertools import combinations 
l=[1,2,3,4,5,6] 

>>> [(x,y,z) for x,y,z in combinations(l,3) if z%y==0 and y%x==0]
[(1, 2, 4), (1, 2, 6), (1, 3, 6)]

Since combinations generates the tuples in list order, you do not then need to check the index of z.

Then your myCOUNT function becomes:

def cnt(li):
 return sum(1 for x,y,z in combinations(li,3) if z%y==0 and y%x==0)

>>> cnt([1,1,1])
1
>>> cnt([1,2,3,4,5,6])
3

This is a known problem.

Here are some timing for the solutions here:

from itertools import combinations 

class DivisionTree:
 def __init__(self, values): 
 # For a division-tree to be connected, we need 1 to be its head
 # Thus we artificially add it and note whether it was actually in our numbers
 if 1 in values:
 self._has_one = True
 values = values[1:]
 else:
 self._has_one = False

 self._graph = 1: 

 for v in values:
 self.insert(v)

 def __iter__(self):
 """Iterate over all values of the division-tree"""
 yield from self._graph

 def insert(self, n):
 """Insert value in division tree, adding it as child of each divisor"""
 self._graph[n] = 

 for x in self:
 if n != x and n % x == 0:
 self._graph[x].append(n)

 def paths(self, depth, _from=1):
 """Return a generator of all paths of *depth* down the division-tree"""
 if _from == 1:
 for x in self._graph[_from]:
 yield from self.paths(depth , _from=x)

 if depth == 1:
 yield [_from]
 return

 if _from != 1 or self._has_one:
 for x in self._graph[_from]:
 for p in self.paths(depth - 1, _from=x):
 yield [_from, *p]


def f1(li):
 return sum(1 for x,y,z in combinations(li,3) if z%y==0 and y%x==0)

def f2(l):
 newlist=[[x,y,z] for x in l for y in l for z in l if (z%y==0 and y%x==0 and l.index(x)<l.index(y) and l.index(y)<l.index(z))]
 return len(newlist)

def f3(a): 
 result = 0
 length = len(a)

 for i in range(length):
 for j in range(i + 1, length):
 for k in range(j + 1, length):
 if a[j] % a[i] == 0 and a[k] % a[j] == 0:
 result += 1

 return result

def f4(l):
 dt = DivisionTree(l)
 return sum(1 for _ in dt.paths(3)) 

def f5(l):
 total = 0
 for mid_i, mid in enumerate(l):
 num_left = sum(1 for x in l[:mid_i] if mid % x == 0)
 num_right = sum(1 for x in l[mid_i+1:] if x % mid == 0)
 total += num_left * num_right
 return total 


if __name__=='__main__':
 import timeit
 tl=list(range(3,155))
 funcs=(f1,f2,f3,f4,f5)
 td=f.__name__:f(tl) for f in funcs
 print(td)
 for case, x in (('small',50),('medium',500),('large',5000)):
 li=list(range(2,x))
 print(': elements'.format(case,x))
 for f in funcs:
 print(" :^10s:.4f secs".format(f.__name__, timeit.timeit("f(li)", setup="from __main__ import f, li", number=1)))

And the results:

'f1': 463, 'f2': 463, 'f3': 463, 'f4': 463, 'f5': 463
small: 50 elements
 f1 0.0010 secs
 f2 0.0056 secs
 f3 0.0018 secs
 f4 0.0003 secs
 f5 0.0002 secs
medium: 500 elements
 f1 1.1702 secs
 f2 5.3396 secs
 f3 1.8519 secs
 f4 0.0156 secs
 f5 0.0110 secs
large: 5000 elements
 f1 1527.4956 secs
 f2 6245.9930 secs
 f3 2074.2257 secs
 f4 1.3492 secs
 f5 1.2993 secs

You can see that f1,f2,f3 are clearly O(n^3) or worse and f4,f5 are O(n^2). f2 took more than 90 minutes for what f4 and f5 did in 1.3 seconds.

This also works, but again, takes too long. There must be a solution beyond brute forcing it... — Aug 12 at 1:49

score 0 · Answer 10 · 2018-08-13 17:33:15Z

Solution in O(M*log(M)) for a sorted list containing positive numbers

As user2357112 has answered, we can count the number of triplets in O(n^2) by calculating for every number the number of its factors and multiples. However, if instead of comparing every pair we go over its multiples smaller than the largest number and check whether they are in the list, we can change the efficiency to O(N+M*log(N)), when M is the largest number in the list.

Code:

def countTriples(myList):
 counts = #Contains the number of appearances of every number.
 factors = #Contains the number of factors of every number.
 multiples = #Contains the number of multiples of every number.

 for i in myList: #Initializing the dictionaries.
 counts[i] = 0
 factors[i] = 0
 multiples[i] = 0

 maxNum = max(myList) #The maximum number in the list.

 #First, we count the number of appearances of every number.
 for i in myList:
 counts[i] += 1

 #Then, for every number in the list, we check whether its multiples are in the list.
 for i in counts:
 for j in range(2*i, maxNum+1, i):
 if(counts.has_key(j)):
 factors[j] += counts[i]
 multiples[i] += counts[j]

 #Finally, we count the number of triples.
 ans = 0
 for i in counts:
 ans += counts[i]*factors[i]*multiples[i] #Counting triplets with three numbers.
 ans += counts[i]*(counts[i]-1)*factors[i]/2 #Counting triplets with two larger and one smaller number.
 ans += counts[i]*(counts[i]-1)*multiples[i]/2 #Counting triplets with two smaller numbers and one larger number.
 ans += counts[i]*(counts[i]-1)*(counts[i]-2)/6 #Counting triplets with three copies of the same number.

 return ans

While this solution will work quickly for lists containing many small numbers, it will not work for lists containing large numbers:

countTriples(list(range(1,1000000)) #Took 80 seconds on my computer
countTriples([1,2,1000000000000]) #Will take a very long time

Fast solution with unknown efficiency for unsorted lists

Another method to count the number of multiples and factors of every number in the list would be to use a binary tree data structure, with leaves corresponding to numbers. The data structure supports three operations:

1) Add a number to every position which is a multiple of a number.

2) Add a number to every position which is specified in a set.

3) Get the value of a position.

We use lazy propagation, and propagate the updates from the root to lower nodes only during queries.

To find the number of factors of every item in the list, we iterate over the list, query the number of factors of the current item from the data structure, and add 1 to every position which is a multiple of the item.

To find the number of multiples of every item, we first find for every item in the list all its factors using the algorithm described in the previous solution.

We then iterate over the list in the reverse order. For every item, we query the number of its multiples from the data structure, and add 1 to its factors in the data structure.

Finally, for every item, we add the multiplication of its factors and multiples to the answer.

Code:

'''A tree that supports two operations:
 addOrder(num) - If given a number, adds 1 to all the values which are multiples of the given number. If given a tuple, adds 1 to all the values in the tuple.
 getValue(num) - returns the value of the number.
 Uses lazy evaluation to speed up the algorithm.
'''
class fen:
 '''Initiates the tree from either a list, or a segment of the list designated by s and e'''
 def __init__(this, l, s = 0, e = -1):
 if(e == -1): e = len(l)-1
 this.x1 = l[s]
 this.x2 = l[e]

 this.val = 0
 this.orders = 

 if(s != e):
 this.s1 = fen(l, s, (s+e)/2)
 this.s2 = fen(l, (s+e)/2+1, e)
 else:
 this.s1 = None
 this.s2 = None

 '''Testing if a multiple of the number appears in the range of this node.'''
 def _numGood(this, num):
 if(this.x2-this.x1+1 >= num): return True
 m1 = this.x1%num
 m2 = this.x2%num
 return m1 == 0 or m1 > m2

 '''Testing if a member of the group appears in the range of this node.'''
 def _groupGood(this, group):
 low = 0
 high = len(group)
 if(this.x1 <= group[0] <= this.x2): return True
 while(low != high-1):
 mid = (low+high)/2;
 if(group[mid] < this.x1): low = mid
 elif(group[mid] > this.x2): high = mid
 else: return True
 return False

 def _isGood(this, val):
 if(type(val) == tuple):
 return this._groupGood(val)
 return this._numGood(val)

 '''Adds an order to this node.'''
 def addOrder(this, num, count = 1):
 if(not this._isGood(num)): return
 if(this.x1 == this.x2): this.val += count
 else :this.orders[num] = this.orders.get(num, 0)+count

 '''Pushes the orders to lower nodes.''' 
 def _pushOrders(this):
 if(this.x1 == this.x2): return
 for i in this.orders:
 this.s1.addOrder(i, this.orders[i])
 this.s2.addOrder(i, this.orders[i])
 this.orders = 

 def getValue(this, num):
 this._pushOrders()
 if(num < this.x1 or num > this.x2):
 return 0
 if(this.x1 == this.x2):
 return this.val
 return this.s1.getValue(num)+this.s2.getValue(num)

def countTriples2(myList):
 factors = [0 for i in myList]
 multiples = [0 for i in myList]

 numSet = set((abs(i) for i in myList))
 sortedList = sorted(list(numSet))

 #Calculating factors.
 tree = fen(sortedList)
 for i in range(len(myList)):
 factors[i] = tree.getValue(abs(myList[i]))
 tree.addOrder(abs(myList[i]))

 #Calculating the divisors of every number in the group.
 mxNum = max(numSet)
 divisors = i: for i in numSet

 for i in sortedList:
 for j in range(i, mxNum+1, i):
 if(j in numSet):
 divisors[j].append(i)
 divisors = i:tuple(divisors[i]) for i in divisors
 #Calculating the number of multiples to the right of every number.
 tree = fen(sortedList)
 for i in range(len(myList)-1, -1, -1):
 multiples[i] = tree.getValue(abs(myList[i]))
 tree.addOrder(divisors[abs(myList[i])])

 ans = 0
 for i in range(len(myList)):
 ans += factors[i]*multiples[i]

 return ans

This solution worked for a list containing the numbers 1..10000 in six seconds on my computer, and for a list containing the numbers 1..100000 in 87 seconds.

You seem to have forgotten to account for triples involving two or three copies of the same number. — Aug 12 at 17:54
Also, if you want to handle negatives, it's not enough to just do i = -i. You also need to account for negative multiples of each number, and assuming the list is sorted no longer guarantees that divisors are on the left and multiples are on the right. — Aug 12 at 17:59
Thank you for pointing out these mistakes. They are fixed now. — Aug 12 at 23:55

Category

Random preview

Faster Python technique to count triples from a list of numbers that are multiples of each other

5 Answers 5

Finding all tuples in O(n2)

Division tree

Usage

Example

Output

Time complexity

Solution in O(M*log(M)) for a sorted list containing positive numbers

Fast solution with unknown efficiency for unsorted lists

Your Answer

Sign up or log in

Post as a guest

Post as a guest

5 Answers 5

5 Answers 5

Finding all tuples in O(n2)

Division tree

Usage

Example

Output

Time complexity

Finding all tuples in O(n2)

Division tree

Usage

Example

Output

Time complexity

Finding all tuples in O(n2)

Division tree

Usage

Example

Output

Time complexity

Finding all tuples in O(n2)

Division tree

Usage

Example

Output

Time complexity

Solution in O(M*log(M)) for a sorted list containing positive numbers

Fast solution with unknown efficiency for unsorted lists

Solution in O(M*log(M)) for a sorted list containing positive numbers

Fast solution with unknown efficiency for unsorted lists

Solution in O(M*log(M)) for a sorted list containing positive numbers

Fast solution with unknown efficiency for unsorted lists

Solution in O(M*log(M)) for a sorted list containing positive numbers

Fast solution with unknown efficiency for unsorted lists

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

What does second last employer means? [closed]

List of Gilmore Girls characters

Confectionery

5 Answers
5

Finding all tuples in O(n²)

5 Answers
5

5 Answers
5

Finding all tuples in O(n²)

Finding all tuples in O(n²)

Finding all tuples in O(n²)

Finding all tuples in O(n²)