Creating an algorithm to swap page order after scanning odd then even pages in a single list

Question

5.00/5 (1 vote)

See more:

Hi all,

I am trying to write a program that simulates scanning pages one side then the other to simulate a duplex scan and then reorder the pages into their logical sequence.
For example
if I scan a bunch pages in the order 1,3,5 then the other side 6,4,2. The second scan you flip the pages so it starts at the last page hence the 6,4,2 sequence. I end up with the page number in order of 1,3,5,6,4,2 with only swapping the numbers I want the sequence to be 1,2,3,4,5,6. (It must swap as the class won't allow adding, inserting removing.)

I have run through a few examples manually below but apart from the start of the swaps being the same I can't see a pattern that I can use to put this into a formula and loop. The numbers below show the scan sequence for various stack size of pages, the next column is the swap order to get them aligned. The next line show the swapped pages and then the next swap sequence
Does anyone see a pattern or better still have an algorithm?

2 sheets of paper 4 sides
1,3,4,2 : 2-4
1,2,4,3 : 3-4
1,2,3,4

3 sheets of paper 6 sides
1,3,5,6,4,2 : 2-6
1,2,5,6,4,3 : 3-6
1,2,3,6,4,5 : 4-5
1,2,3,4,6,5 : 5-6
1,2,3,4,5,6

4 sheets of paper 8 sides
1,3,5,7,8,6,4,2 : 2-8
1,2,5,7,8,6,4,3 : 3-8
1,2,3,7,8,6,4,5 : 4-7
1,2,3,4,8,6,7,5 : 5-8
1,2,3,4,5,6,7,8

5 sheets of paper 10 sides
1,3,5,7,9,10,8,6,4,2 : 2-10
1,2,5,7,9,10,8,6,4,3 : 3-10
1,2,3,7,9,10,8,6,4,5 : 4-9
1,2,3,4,9,10,8,6,7,5 : 5-10
1,2,3,4,5,10,8,6,7,9 : 6-8
1,2,3,4,5,6,8,10,7,9 : 7-9
1,2,3,4,5,6,7,10,8,9 : 8-9
1,2,3,4,5,6,7,8,10,9 : 9-10
1,2,3,4,5,6,7,8,9,10

6 sheets of paper 12 sides
1,3,5,7,9,11,12,10,8,6,4,2 : 2-12
1,2,5,7,9,11,12,10,8,6,4,3 : 3-12
1,2,3,7,9,11,12,10,8,6,4,5 : 4-11
1,2,3,4,9,11,12,10,8,6,7,5 : 5-12
1,2,3,4,5,11,12,10,8,6,7,9 : 6-10
1,2,3,4,5,6,12,10,8,11,7,9 : 7-9
1,2,3,4,5,6,7,10,8,11,12,9 : 8-9
1,2,3,4,5,6,7,8,10,11,12,9 : 9-12
1,2,3,4,5,6,7,8,9,11,12,10 : 10-12
1,2,3,4,5,6,7,8,9,10,12,11 : 11-12
1,2,3,4,5,6,7,8,9,10,11,12

Posted 28-Feb-13 17:37pm

Coding123456

Add a Solution

2 solutions

Solution 1

I don't see a pattern, but the algorithm is just the one you applied.

1/ Write the sequence of the sides, say 1,3,5,7,8,6,4,2
2/ 1 is already well placed
3/ 3 is out of sequence and should be swapped with 2 -> search for side 2
4/ swap sides 3 and 2, i.e. 2-8, giving 1, 2, 5, 7, 8, 6, 4, 3
5/ 5 is out of sequence and should be swapped with 3 -> search for side 3
6/ swap sides 5 and 3, i.e. 3-8, giving 1,2,3,7,8,6,4,5
...

C++

i= 2
while i+1 < N
  /* S[i] is misplaced */
  search side i in S[i+1..N], let S[j]
  swap S[i] with S[j]
  /* S[i] is now well placed */

Besides that, it is probably worth to rethink the problem by simplifying it: one one hand ignore the reversal of the even pages; on the other hand, ignore the de-interleaving of the odd and even pages. In both cases the pattern will simplify and mabe allow you to solve the general case.

Posted 2-Mar-13 6:56am

YvesDaoust

Updated 2-Mar-13 7:18am

v2

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Coding123456 · Accepted Answer · 2013-04-08T03:51:00

I believe I have a way to solve this. I need to re-order the even pages (the second batch of scanning) one page at a time as they are scanned. Something I hadn't thought of doing. On the first scan, scan of all the even pages and second scan the odd ones, reordering as you go.
The examples below show 2,3 and 4 sheets.

2 sheets
1,3 first scan all odd pages
1,3,4 scan 1st page of the even batch
1,3,4,2 swap 4:2
1,2,4,3 swap 4:3
1,2,3,4 final order

3 sheets
1,3,5 scan
1,3,5,6 scan
1,3,5,6,4 swap 5:3
1,3,4,6,5 swap 5:4
1,3,4,5,6 scan
1,3,4,5,6,2 swap 6:2
1,2,4,5,6,3 swap 6:3
1,2,3,5,6,4 swap 6:4
1,2,3,4,6,5 swap 6:5
1,2,3,4,5,6

4 sheets
1,3,5,7 scan
1,3,5,7,8 scan
1,3,5,7,8,6 swap 6:4
1,3,5,6,8,7 swap 6:5
1,3,5,6,7,8 scan
1,3,5,6,7,8,4 swap 7:3
1,3,4,6,7,8,5 swap 7:4
1,3,4,5,7,8,6 swap 7:5
1,3,4,5,6,8,7 swap 7:6
1,3,4,5,6,7,8 scan
1,3,4,5,6,7,8,2 swap 8:2
1,2,4,5,6,7,8,3 swap 8:3
1,2,3,5,6,7,8,4 swap 8:4
1,2,3,4,6,7,8,5 swap 8:5
1,2,3,4,5,7,8,6 swap 8:6
1,2,3,4,5,6,8,7 swap 8:7
1,2,3,4,5,6,7,8

The code in VB
_SwapPage is initially set to the number of pages scanned in the first batch. ie number of odd pages

VB

Private Sub DuplexSwapOnTheFly()
     Dim LastImage As Integer = AcquiredImages.Count
     Dim i As Integer

     'the first scan of the reverse side is not swapped
     If LastImage - _SwapPage = 1 Then Exit Sub

     For i = _SwapPage To LastImage - 1
         AcquiredImages.Swap(LastImage, i )
     Next
     _SwapPage -= 1
 End Sub