StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It looks like this algorithm can loop forever, oscillating between two or more states. I determined this experimentally using the following Python program:</p> <pre><code>def mean(seq): if len(seq) == 0: raise IndexError("didn't expect empty sequence for mean") return sum(seq) / float(len(seq)) def dist(a,b): return abs(a-b) def mean_dist(x, k, a): neighbors = {p for p in a if p != x} neighbors = sorted(neighbors, key=lambda p: dist(p,x)) return mean([dist(x, p) for p in neighbors[:k]]) def frob(a,b,k, verbose = False): def show(msg): if verbose: print msg seen_pairs = set() iterations = 0 while True: iterations += 1 show("Iteration #{}".format(iterations)) a_star = {x for x in a if mean_dist(x, k, a) > mean_dist(x,k,b)} b_star = {x for x in b if mean_dist(x, k, a) < mean_dist(x,k,b)} a_temp = {x for x in a if x not in a_star} | b_star b_temp = {x for x in b if x not in b_star} | a_star show("\tA`: {}".format(list(a_star))) show("\tB`: {}".format(list(b_star))) show("\tA becomes {}".format(list(a_temp))) show("\tB becomes {}".format(list(b_temp))) if a_temp == a and b_temp == b: return a, b key = (tuple(sorted(a_temp)), tuple(sorted(b_temp))) if key in seen_pairs: raise Exception("Infinite loop for values {} and {}".format(list(a_temp),list(b_temp))) seen_pairs.add(key) a = a_temp b = b_temp import random #creates a set of random integers, with the given number of elements. def randSet(size): a = set() while len(a) < size: a.add(random.randint(0, 10)) return a size = 2 k = 1 #p equals one because I don't feel like doing vector math today while True: a = randSet(size) b = randSet(size) try: frob(a,b, k) except IndexError as e: continue except Exception as e: print "infinite loop detected for initial inputs {} and {}".format(list(a), list(b)) #run the algorithm again, but showing our work this time try: frob(a,b,k, True) except: pass break </code></pre> <p>Result:</p> <pre><code>infinite loop detected for initial inputs [10, 4] and [1, 5] Iteration #1 A`: [10, 4] B`: [1, 5] A becomes [1, 5] B becomes [10, 4] Iteration #2 A`: [1, 5] B`: [10, 4] A becomes [10, 4] B becomes [1, 5] Iteration #3 A`: [10, 4] B`: [1, 5] A becomes [1, 5] B becomes [10, 4] </code></pre> <p>In this case, the loop never terminates because A and B continually switch entirely. While experimenting with larger set sizes, I found a case where only some elements switch:</p> <pre><code>infinite loop detected for initial inputs [8, 1, 0] and [9, 4, 5] Iteration #1 A`: [8] B`: [9] A becomes [0, 1, 9] B becomes [8, 4, 5] Iteration #2 A`: [9] B`: [8] A becomes [0, 1, 8] B becomes [9, 4, 5] Iteration #3 A`: [8] B`: [9] A becomes [0, 1, 9] B becomes [8, 4, 5] </code></pre> <p>Here, elements 8 and 9 move back and forth while the other elements stay in place.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload