Can someone give me some ideas of algorithm for this card question?

Question

Problem

There is a $N$ by $1$ long card consisting of $N$ square cards, each having the number $1, 2, \cdots, N$ regardless of the sequence of cards. Find whether or not the long card could be in order, by folding it either backward or forward. (Suppose that there is no consideration of thickness of cards).

For example, there is a long card is a sequence of $\{5,3,2,1,4\}$. Then if we can make it in order by folding like the following:

I know my picture is not seen as the square cards set. However, my poor English cannot describe this problem well. I hope to make C-code or Matlab-code solving this problem. When a sequence is given, I want to check the sequence can be done like above or not(i.e. I want to display "Yes" or "No").

Sorry and thank you for reading my question.

Answer 1

I think this problem may be similar to figuring out whether a maze is a simple alternating transit maze: http://www.math.stonybrook.edu/~tony/mazes/satmaze.html

In that case the solution would be whether when you write the numbers out like this: $n_1 n_2\cdots n_N$, you can draw a line that visits the numbers $1\cdots N$ in order, passing alternatingly above and below the number line, without crossing itself.

If I can produce reasonable code for this, I will submit it as well.

Answer 2

The following two questions are equivalent:

1. "Can the cards be folded to put them in increasing order, when they are labeled in a specified arbitrary order?"

2. "Can the cards be folded to produce a specified arbitrary order, when they are labeled in increasing order?"

The relevant result was proved by Koehler in 1968 ("Folding a Strip of Stamps"):

An $n$-permutation $p$ is a folding if and only if the circular order

$p(i) < p(j) < p(i + 1) < p(j + 1)$

does not occur when $i$ and $j$ are either both odd or both even. By circular order is meant any circular permutation of the inequalities above.

E.g., your $5,3,2,1,4$ is determined to be a folding of $1,2,3,4,5$ by checking that none of its circular permutations contain a subsequence of the form $i,j,i+1,j+1$ with $i$ and $j$ of the same parity. On the other hand, $5,3,2,4,1$ is not such a folding because it has the circular permutation $1,5,3,2,4$, which contains the forbidden subsequence $1,3,2,4$ ($i=1,j=3$).

On the web, search "folding labeled stamps" for lots of online sources.

---

Here's an outline of an unoptimized algorithm based directly on the above result:

def forbidden(n):
    # returns a list of all "forbidden" pairs; i.e., (i,j) such that  
    # 1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1, i ≠ j, i ≡ j (mod 2)

def is_subseq(x,y):
    # returns True if x is a subsequence of y, else returns False

def is_folding(x):
    # returns True if sequence x is a folding, else returns False
    # cyc_perms is a list of all cyclic permutations of sequence x
    for cyc_perm in cyc_perms:
        for (i,j) in forbidden(len(x)):
            if is_subseq([i,j,i+1,j+1],cyc_perm): return False
    return True

As a check on the algorithm's correctness, I programmed this in Python and used it to reproduce the correct values of the number of foldings as a function of $N$ (just for $N \le 10$, due to time constraints).