Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: list Algorithms
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 18:37pm
Rate this: bad
good
Please Sign up or sign in to vote.

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
...
 
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.
  Permalink  
v2
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 3

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
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
  Permalink  

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

  Print Answers RSS
0 OriginalGriff 5,130
1 DamithSL 4,237
2 Maciej Los 3,700
3 Kornfeld Eliyahu Peter 3,470
4 Sergey Alexandrovich Kryukov 2,846


Advertise | Privacy | Mobile
Web03 | 2.8.141216.1 | Last Updated 8 Apr 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100