/sci/ - Science & Math

Archives of previous threads for reference:
http://4watch.org/superstring/
http://archive.gentoomen.org/cgi-board.pl/sci/thread/3734198

103

n^13 or n^14?

Non-math, gayfag guess.

14! derp

>>3751172
this! lol

>troll is too stupid to include "randomly out of all possible episodes"
too easy

>>3751172
Nope, we already have the (trivial) lower bound n+n!−1.

>>3751177
>this! lol
You have only once again reconfirmed my suspicion that /sci/ is one of the boards with the largest proportion of underage b&.

14!/2

What we know at the moment is that it can be done in <span class="math">\sum_{i=1}^n i![/spoiler] episodes (where n=14 for the original problem).

Here's a Python implementation of the currently known algorithm:
http://pastebin.com/aNwANugC

And some explanation of what's going on:
http://math.stackexchange.com/questions/15510/what-is-the-shortest-string-that-contains-all-permutat
ions-of-an-alphabet

Another way of generating the same string:
http://www.notatt.com/permutations.pdf

However, as of yet it seems no one has found a proof that the algorithm is optimal.

More links with discussion of the problem:
http://www.reddit.com/r/math/related/foj1l/the_shortest_string_containing_all_permutations/
http://oeis.org/A180632
http://stackoverflow.com/questions/2253232/generate-sequence-with-all-permutations/2274978
http://forums.xkcd.com/viewtopic.php?f=17&t=68643

I think I have a proof of the lower bound n! + (n-1)! + (n-2)! + n-3 (for <span class="math">n \geq 2[/spoiler]). I'll need to do this in multiple posts. Please look it over for any loopholes I might have missed.

As in other posts, let n (lowercase) = the number of symbols; there are n! permutations to iterate through.

The obvious lower bound is n! + n-1. We can obtain this as follows:

Let
L = the running length of the string
<span class="math">N_0[/spoiler] = the number of permutations visited
<span class="math">X_0 = L - N_0[/spoiler]

When you write down the first permutation, <span class="math">X_0[/spoiler] is already n-1. For each new permutation you visit, the length of the string must increase by at least 1. So <span class="math">X_0[/spoiler] can never decrease. At the end, <span class="math">N_0 = n![/spoiler], giving us <span class="math">L \geq n! + n-1[/spoiler].

I'll use similar methods to go further, but first I'll need to explain my terminology...

Edges:

I'm picturing the ways to get from one permutation to the next as a directed graph where the nodes correspond to permutations and the edges to ways to get from one to the next. A k-edge is an edge in which you move k symbols from the beginning of the permutation to the end; for example,

1234567 -> 4567321

would be a 3-edge. Note that I don't include edges like

12345 -> 34512

in which you pass through through a permutation in the middle (in this case 23451). This example would be considered two edges:

12345 -> 23451
23451 -> 34512

From every node there is exactly one 1-edge, e.g.:

12345 -> 23451

These take you around in a cycle of length n. A 2-edge moves the first two symbols to the end. A priori, it could either reverse or maintain the order of those two symbols:

12345 -> 34521
12345 -> 34512

But the second, as already stated, is not counted as a 2-edge because it is a composition of two 1-edges. So there is exactly one 2-edge from every node.

1-loops:

I call the set of n permutations connected by a cyclic path of 1-edges a 1-loop. There are (n-1)! 1-loops.

The concept of 1-loops is enough to get the next easiest lower bound of n! + (n-1)! + n-2. That's because to pass from one 1-loop to another, it is necessary to take a 2-edge or higher. Let us define:

<span class="math">N_1[/spoiler] = the number of 1-cycles completed or that we are currently in
<span class="math">X_1 = L - N_1 - N_2[/spoiler]

The definition of <span class="math">N_1[/spoiler] is a bit more complicated than we need for this proof, but we'll need it later. You might ask, isn't <span class="math">N_1[/spoiler] just one more than the number of completed 1-cycles? No! When we have just completed a 1-cycle, it is equal to the number of completed 1-cycles.

In order to increment <span class="math">N_1[/spoiler], we have to take a 2-edge, which increases L by 2 instead of 1. Therefore <span class="math">X_1[/spoiler] can never decrease. Since <span class="math">X_1[/spoiler] starts out with the value n-2, and we have to complete all (n-1)! 1-loops, we get the lower bound n! + (n-1)! + n-2.

2-loops:

Suppose we enter a 1-loop, iterate through all n nodes (as is done in the greedy palindrome algorithm), and then take a 2-edge out. The edge we exit by is determined by the entry point. The permutation that the 2-edge takes us to is determined by taking the entry point and rotating the first n-1 characters, e.g.:

12345
is taken by n-1 1-edges to
51234
which is taken by a 2-edge to
23415

If we repeat this process, it takes us around in a larger loop passing through n(n-1) permutations. I call this greater loop a 2-loop.

The greedy palindrome algorithm uses ever-larger loops; it connects (n-k+1) k-loops via (k+1)-edges to make (k+1)-loops. But I haven't been able to prove anything about these larger loops yet.

The tricky thing about 2-loops is that which 2-loop you're in depends on the point at which you entered the current 1-loop. Each of the n possible entry points to a 1-loop gives you a different 2-loop, so there are n*(n-2)! 2-loops, which overlap.

And now for the proof of the n! + (n-1)! + (n-2)! lower bound...

To review:
n = alphabet length
L = running string length
<span class="math">N_0[/spoiler] = number of permutations visited
<span class="math">X_0 = L - N_0[/spoiler]
<span class="math">N_1[/spoiler] = number of 1-cycles completed or that we are currently in
<span class="math">X_1 = L - N_1 - N_2[/spoiler]

In order to increase <span class="math">N_1[/spoiler], you must jump to a new 1-cycle -- having completed the one you are leaving. That means the next permutation P' in the 1-cycle (following your exit point P) is one you have already visited. Either you have at some point entered the 1-cycle at P', or this is the second or greater time you've visited P. If you have ever entered the 1-cycle at P', leaving at P by a 2-edge will not take you to a new 2-cycle; you will be in the same 2-cycle you were in when you entered at P'.

So these are the available ways to enter a 2-cycle you've never been in before:
* take a 3-edge or higher
* take a 2-edge but don't increase <span class="math">N_1[/spoiler]
* take a 2-edge from a permutation P that you were visiting for the second or greater time

In the first two cases, <span class="math">X_1[/spoiler] increases by 1 in the step under consideration. In the third case, <span class="math">X_1[/spoiler] must have increased by 1 in the previous step. Because of this third case, it is convenient to regard any series of edge traversals that takes you through permutations you've already visited as a single step. Then if we define

<span class="math">N_2[/spoiler] = number of 2-cycles visited
<span class="math">X_2 = L - N_0 - N_1 - N_2[/spoiler]

the quantity <span class="math">X_2[/spoiler] does not decrease in any step. Since 2-cycles are n(n-1) long, you must visit at least (n-2)! 2-cycles. <span class="math">X_2[/spoiler] is initially n-3, giving us the lower bound

<span class="math">L \geq n! + (n-1)! + (n-2)! + n-3[/spoiler].

Guise!
Itsa trick question!

>>What is the least number of episodes you would have to watch?

I can watch each episode 1,000 times but I've still only watched 14 episodes.

So the answer is just 14. (no factorial) :p I win!

>>3751212

>Ops face when he realizes how idiotic his attempt to answer the question is

>>3751212
>>3751227
you knew what I mean. I could say if each ep was 30min, then how many hours would you have to watch, but that would be just semantics

Someone in another thread wanted the two n=5 strings, so reposting from last thread:

The "standard" solution given by the algorithm we've seen expressed several ways now which I think are equivalent:
(I'm just listing the cycles, so 01234 means it goes through the permutations 01234,12340,23401,34012,40123.)
01234 12304 23014 30124
12034 20314 03124 31204
20134 01324 13204 32014

10234 02314 23104 31024
02134 21304 13024 30214
21034 10324 03214 32104

The "alternate" solution:
01234 12304 23014 30124
12034 20314 03124 31204
20134 01324 13204 32014

10243 02413 24103 41023
02143 21403 14023 40213
21043 10423 04213 42103

The alternate solution deviates from the standard one in the central step where the next permutation only shares one symbol with the previous permutation. Where the standard solution hits the permutation 10234, the alternate one uses 10243. It continues on in the same manner as the standard one except that the 3 and 4 are reversed.

So I've come to the conclusion that http://www.notatt.com/permutations.pdf is complete bullshit. Anyone disagree?

>>3751251
It would be nice to hear some reasoning for that conclusion. I don't see any problem with what he wrote.

Greetings again, good sir.

Let's get all the 14! and 14*14! derps out of the way now so the big boys can talk math

Alright, after that pretentious statement, I'll acknowledge that I'm not a big boy at math at all, I'm quite a novice.

Here's my thoughts, from the ground up:

Initially, intuition sets the upper bound at 14*14! (1.22 * 10^12), for obvious reasons. Extending beyond that is redundancy. That gentleman from the other night showed that a more workable upper bound is the sum of the factorials (9.39 ^ 10.)

That's a huge step forward. What about the lower bounds? Intuitively, 13 + 14! would be the initial lower bound, being the 13 necessary as filler for the first permutation, and the possibility of a sequential permutation for each episode added.

We know that this isn't true-- that you can't add one episode and get one new permutation continuously. That much is intuitive. How would one go about proving that?

I'm trying to look at some sort of pattern in the attainability of new permutations for n different episodes, but I wouldn't even know where to start.

>>3751251
how is it bullshit? its very solid

>>3751288
ha. /sci/ has improved a great deal when it comes to that in these threads. The first one was full of 14!*14 /thread comments, people telling them

>>3751313
9.39 * 10^10, I meant to say.

>>3751313
this is my line of thinking. In the most brute force way of doing the problem is just the episode numbers. A slightly more sophisticated way of doing that is looking at the permutations. Even better than that, We discovered we could use cycle groups, i.e. each group represents its permutations, and only the order of the cycle group matters.

This is an important innovation because the order of cycle groups is much more succinct and generalizable than just looking at permutations.

Two questions must be asked:
In an efficient string, must the permutations of a cycle group be listed consecutively? i.e. for n=6, does each efficient string contain 1,2,3,4,5,6,1,2,3,4,5? If the answer is yes, that means a cycle groups only appear once.

Is there a way to generalize the algorithm based on cycle groups?

>>3751313
The moves where you add a string of length 1 to get the next permutation take the symbol from the start of the last permutation and appends it to the end. This rotates the symbols in the permutation, and after n such moves you're back where you started:

12345
23451
34512
45123
51234
12345

You can only go in between the n-cycles with a move that adds a string of at least 2. Since there are (n-1)! - 1 such n-cycles, that gives the n! + (n-1)! + n-2 lower bound.

I think I've proven n! + (n-1)! + (n-2)! + n-3 as a lower bound also, but my reasoning needs to be checked by other eyes:
>>3751197
>>3751199
>>3751204
>>3751205
>>3751207

>>3751197
Ok, I'm going to read through your posts carefully. I like that you're looking at the places where you change cycle groups, but one thing I'm thinking is, how do we know that NOT completing a cycle graph would lead to a better solution. i.e. maybe we could start with 1,2,3,4,5,6,7 then put 2,3,4,5,6,7,1 somewhere later down the road

OK, I'm almost...
not quite, but almost...
ready to conjecture that the number of different ways of achieving this (likely optimal) sequence length is:
the product from 1 to n-3 of k!

>>3751343
After seeing these cycle groups mentioned many times, I think I'm starting to get it..

The 123451234 makes sense as starting with the natural pattern and obtaining 4 additional permutations promptly, and from there you'd take the 234 at the end and start 15, then repeat the first four for 234152341?

123451234
-----------234152341
And so on, until you get back to 123451234? That makes sense, but what does this accomplish? Does it just give us a pattern to run with?

>>3751370
>how do we know that NOT completing a cycle graph would lead to a better solution
I assume you mean wouldn't. At the moment, we don't know that. But leaving a cycle early and coming back to finish it later has an associated cost. And what I'm doing is trying to carefully quantify that cost. Doing so only gives you a lower bound. It might be that when n is large you can avoid the really long moves of the standard algorithm by making a few strategic early departures from the smaller loops.

>>3751373
Oh damn. This is one question I asked last time. I don't think the world is ready for that madness. in those cases where only one element overlaps, ALL (n-1)!/2 cycle groups are up for grabs. luckily, for n=4 and n=5 this only happens once in the middle, but how do we know this doesn't happen again.

Also I think I have figured something out. We only need to prove that the first half is efficient, because these are all palindromes. i.e. the proof you make with the first (n-1)!/2 cycle groups is guarentteed to work withe the second half

>>3751370
This was my initial thought, too.

So with the cycle groups, it's 1 addition per permutation until switching between cycle groups, at which point it's 2? Are there larger gaps in between there, like moving from one set of cycle groups to the next?

And would I be asking too much if you explained
Since there are (n-1)! - 1 such n-cycles" why this is true?

Thanks a bunch mr. mathematicians

>>3751407
>>3751366
Sorry, that should be
>Since there are (n-1)! such n-cycles
(n-1)! - 1 is the number of times you have to move between n-cycles. And the reason there are (n-1)! n-cycles is simple: n! permutations, n in each n-cycle, so (n-1)! n-cycles.

>>3751384
Yes. But I'm still not sure how to choose the groups. Because sometimes you have more than one option. Check the google doc for an explanation of that. Please comment on it if you want changes or additions

>>3751403
Oops, you're right. I mean it wouldn't. Yeah it's all a cost benefit thing. Staying in a cycle means we'd be giving up the chance to have a 1-edge as the other poster calls it. And the total amount of these should be low as possible. But what if sacrificing a 1-edge for a 2-edge, meant we could avoid higher edges along the way?

Like one thing that keeps appearing is the n-1 edge, i.e. when only one digit overlaps between cycle groups. Those points are very high cost, and occur in the middle of n=4 and n=5. how do we know those can't be avoided with incomplete cycle groups

>>3751407
when you switch between cycle groups, there is variable cost. For example in n=4, sometimes there needs to be an addition of 2, sometimes 3. check the google doc listed at the top for an explanation.

In our algorithm that produces a palindrome sequence, we'd always been prioritizing low edge numbers. i.e. cycle groups are ALWAYS completed (you'd never have 12345124, because that interrupts the group.) then you always try and get a 2-edge. The way I see it, its all about making the sum of edges numbers low as possible. The derp 14!*14 way of doing it would involve n-edges, i.e. no overlap

>>3751441
>Those points are very high cost, and occur in the middle of n=4 and n=5. how do we know those can't be avoided with incomplete cycle groups
For large n (meaning n>4), we don't know that yet. For n=4, according to the n!+(n-1)!+(n-2)!+n-3 argument, it may be possible to avoid taking the 3-edge, but not without doing something else of equal cost, specifically either repeating a permutation you've already been over, or taking a 2-edge that doesn't gain you anything.

>>3751441
>>3751474
I think you either forgot to post the Google doc, or your post didn't go through, because I don't see it.

>>3751476
do we know any alternative sequences for n=4? Hopefully we can show that repeating a permutation is never going to be const efficient
>>3751492
oops, https://docs.google.com/document/d/1AXXx1516LLq3wpiIZT_FayLnp6Q7xw8JlmFqsyyoy8Y/edit?hl=en_US&pl
i=1

Guys, I think this was way easier than we thought.
The proof of
>>3751373
(or finding a different answer for it) seems much harder.

>>3751507
Easier than we thought? Most people, including me thought this was gonna be a snap at first. But 5 minutes into it, I realized there are so many paths and options to account for. Even worse, is that there are multiple efficient sequences.

But finding out how many relies on that initial question. I think if we truly understood why the sum of factorials works, we'd know how many options there are. My body isn't ready for that second question though.

>>3751204
That's a great way to think about it, only looking at the gaps. With your permission, I'd like to add this to my google doc under the tag Anonymous or with any tripcode you might use

>>3751441
>Yes. But I'm still not sure how to choose the groups. Because sometimes you have more than one option. Check the google doc for an explanation of that. Please comment on it if you want changes or additions

The simple rule is that whenever you have to add n symbols to the string to get the next permutation, they should be the n symbols from the beginning of the previous permutation, in reverse order.

This gives you a series of nested loops, each of which rotates the first certain number of characters of the string.

For n=4:
http://pastebin.com/TgPzZeZu

Given any permutation, you can figure out where it will be found in this cycle by rotating the 4 until it's at the end, then rotating the first 3 characters until the 3 is at the end, and so on. This guarantees you'll hit all permutations.

>>3751541
Feel free to do so.

Actually, what we might want is a small wiki for this sort of stuff. By which I mean collaborative work on this and future math problems.

>>3751556
Er, but sometimes there are 2 or more cycle-groups to choose from.
see >>3751241

Answer comin up.
Damn it took a long time to type.

Thanks for showing me the google doc and bringing me up to speed. I'll ponder my feeble mind on it throughout the week.

I doubt I'll be able to provide any insightful answers, but as someone who's intensely interested in understanding what's going on, I might stumble upon the right questions to ask.

>>3751570
doesn't /sci/ have a wiki? If not it should have one for explorations in math
>>3751621
answer to?

>>3751621
cant wait

>>3751588
It's a rule, not the only rule. I don't pretend to know all possible strings of sum-of-factorial length.

But as far as generalizations go:

I think the standard algorithm can be generalized by replacing the step that moves the first k symbols to the end of the permutation in the reverse order, e.g. (with k=4, n=5)

43201 -> 10234

with any step that moves the kth symbol to the end, followed by the (k-1)th symbol, followed by the first (k-2) symbols in arbitrary order, e.g.

43201 -> 10243.

This is the sort of generalization that gives you the second n=5 string.

Another observation:

In both the standard algorithm and the generalized one, the moves in each k-loop preserve the cyclic ordering of n-k+1 of the symbols, specifically the n-k+1 symbols at the beginning of the permutation at the entry point of the loop, and also at the entry point of each (k-1)- subloop. This is important to verifying that the generalized algorithm hits all permutations. Don't have an explanation of this ready-typed, though, and I'm a bit tired.

Yes, easier than we thought. Hopefully I didn't make a mistake and embarrass myself

Let a k-iteration be the process of adding k numbers in a row without making a new permutation, such that the next number will make a new permutation (the other guy called it a k-edge)
so 1234 -> 2341 would require a 0 iteration
1234 -> 3421 would require a 1 iteration and some 0 iterations


Assume x is the highest number of permutations you can get with j0 0-iterations, j1 1-iterations, j2 2-iterations, up to jk k-iterations. Now, we need to move up to a*x permutations, where a is an integer. Clearly, we must use at least one permutation of order higher than k, and if there is a solution using (a*j1) 1-iterations, (a*j2) 2-iterations, up to (a*jk) k-iterations, along with (a-1) k+1 iterations, it is the most efficient way to get 2x permutations.
Applying this to the problem, we know that the most efficient way to get n permutations (starting from a permutation) is to use n-1 0-iterations. Therefore, the most efficient way to get n*(n-1) permutations is to use n-2 1-iterations and (n-1)*(n-1) 0-iterations, as we have seen.

>>3751636
Now I just have to show that those iterations actually add up to sum(k!)

>>3751636
>Clearly, we must use at least one permutation of order higher than k
Why is this?

>>3751636
Or when you say
>Assume x is the highest number of permutations you can get with j0 0-iterations, j1 1-iterations, j2 2-iterations, up to jk k-iterations.
do you mean for the <span class="math">j_i[/spoiler]s to be arbitrary, and x is the highest you can get with any values of the <span class="math">j_i[/spoiler]s? Because you can get to any permutation using only 1- and 2- iterations.

>>3751646
Hmm, I was trying to do it a bit differently but it became a pain so i wrote that up. Perhaps I should go back to try the other way.

>>3751636
what do you mean by move up to a*x permutations.
I'm not actually sure how this lower bounds the problem

>>3751652
>Because you can get to any permutation using only 1- and 2- iterations.
Are you sure? Its a pretty strict restraint to have to resume making more permutations after every couple digits

>>3751691
1-iterations allow you to rotate the string.
Using a 2-iteration followed by (n-2) 1-iterations, we can exchange the first two elements:

12345
34521
45213
52134
21345

And by conjugating that with a rotation, we can exchange arbitrary adjacent elements. And from there you can generate any permutation by moving the element you want first up to first place, the element you want second into second place, and so on.

>>3751630
An implementation of the generalized algorithm:
http://pastebin.com/D16PrjvR

well shit
I'll blame the fact that its 3am

>>3751626
Found it:
http://sciref.wikispaces.com/message/list/home

>>3751769
it's ok, we'll continue this. I'm still blown away by the follow up problem. My mind is broken, it's time for me to watch anime.

>>3751626
If /sci/ has a wiki I couldn't find it. In either case, I propped one up real quick, it should be easy enough to maintain for this sort of stuff. If a better one exists then dropping this one's easy enough.

http://mathsci.wikia.com/wiki//sci/_-_Math_%26_Science_Wiki

using the iteration notation, if each new element yielded a new permutation, then the string would have n elements from the first permutation + (n-1)!-1 element for the remaining permutation. so S=n+(n-1)!-1

but since you can't use only 0-iterations, this isn't the case. each i-iteration has an added cost of i. you use <span class="math">j_i[/spoiler] i-iterations. the maximum of i is n-2, because that is the number of elements you'd add if the overlap was only 1 element. So the goal would be to minimize
<span class="math">\sum_{i=1}^{n-1} i*j_i[/spoiler]

>>3751809
ah cool joining. Next week I'll post another, easier but quite peculiar exploration. It involves polynomials, series, and pascals triangle.

/sci/ - Math & Science

Yep.

>>3751860
just like it was meant to be.
can you add the google doc?

>>3751869
Aye, I just plopped it all on there. I'll organize it into something intelligible tomorrow, Kaiji just ruined my brain.

http://www.youtube.com/watch?v=OeLxUVACQF0

So something that could be important:
a 0-iteration switches the order of no elements (it just rotates the cycle without moving the cycle around). A 1-iteration can switch 2 elements around. A 2-iteration can switch 3 elements around. Basically, a k iteration can switch k+1 elements around in the cycle.
Example: A 1-iteration can take (1 2 3 4 5) to (1 2 4 3 5), and a 3 iteration can take (1 2 3 4 5) to (4 3 2 1 5) (this is allowing any number of 0 iterations). The important thing is that a k-2 iteration, combined with some number of 0 iterations, can do things that (k-3) 1-iterations + an arbitrary number of 0 iterations CANNOT do (for example, to rotate k-1 elements).
For example, a 3 iteration could take (1 2 3 4 5) to (4 1 2 3 5), but 2 1-iterations could not.
This seems like it could be generalized without too much difficulty to state that iterations with a total weight <= k-3 are weaker than a single k-2 iteration.

>>3751914
oops, i think k should be n for most of that, I don't think its true for k < n-2

>>3751914
k should be n for most of this

>>3751914
So I guess you're defining adjacency for the cycles. If a new permutation requires a 1-iteration, the cycle group it belongs to is adjacent to the previous. Adjacency is neither reflexive or transitive.

i.e. (1 2 3 4) is adjacent to (1 4 2 3) which is adjacent to (1 2 4 3). But (1 4 2 3) is not adjacent to (1 2 3 4) which is not adjacent to ( 1 2 4 3)

>>3751949
would you mind reposting? Also does /sci/ have an archive? because when I tried searching for thread I, I only found the opening post

>>3751914
>For example, a 3 iteration could take (1 2 3 4 5) to (4 1 2 3 5), but 2 1-iterations could not.
You only need a single 1-iteration (combined with 0-iterations) to do that:
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
1 2 3 5 4 (the 1-iteration)
2 3 5 4 1
3 5 4 1 2
5 4 1 2 3
4 1 2 3 5

>>3751953
The gentooman archive does archive things, but um. I can only ever retrieve individual posts, not the entire threads.

>>3751953
I'll just leave it at this - this is what happens when you start typing before you're done thinking about stuff:

So something that could be important:
a 0-iteration switches the order of no elements (it just rotates the cycle without moving the cycle around). A 1-iteration can switch 2 elements around. A 2-iteration can switch 3 elements around. Basically, a k iteration can switch k+1 elements around in the cycle.
Example: A 1-iteration can take (1 2 3 4 5) to (1 2 4 3 5), and a 3 iteration can take (1 2 3 4 5) to (4 3 2 1 5) (this is allowing any number of 0 iterations). The important thing is that a k iteration, combined with some number of 0 iterations, can do things that (k-1) 1-iterations + an arbitrary number of 0 iterations CANNOT do (for example, to rotate k+1 elements).
For example, a 3 iteration could take (1 2 3 4 5) to (4 1 2 3 5), but 2 1-iterations could not.
This seems like it could be generalized without too much difficulty to state that iterations with a total weight < k are weaker than a single k iteration.


Anyway, the goal would be more to show the triangle inequality with distance than to define adjacency. It doesn't seem like it would be that hard, but I'm too tired atm.

>>3751953
Thread 1 happened at the same time as changes in 4chan's HTML code that broke the archiver for a while, but see
>>3751122
for a copy.
But Thread II and this one are showing up on archive.gentoomen.org just fine.

>>3751965
Hmm
Make it: (1234567) -> (4123567)

>>3751718
should be 0-iteration and 1-iteration.
Was confused since the k-iteration is the (k+1)-edge from before.

>>3751953
I think I understand your point, that sometimes the amount of overlap will be 1,2..n. The only case I've looked at extensively is n=4. In that case, you'd have 0-iterations (obviously) as well as 1-iterations and 2-iterations (maximum). I wonder if for case n, if you must have a non-zero number of 0,1,2...n-2 iterations in the efficient process.

I wonder if there are any situations where a k iteration could be strictly stronger than every sum k set of iterations.

>>3752034
nevermind thats dumb. My intelligence has fallen enough that I'll force myself to sleep.