Not sure if this is the correct community to post this is. But as I see this problem as an interesting puzzle to solve, I'd thought to give it a shot...
Let`s say we have:
- N collections of parts: A, B,C,D,...etc
- Each collection consists of n parts: 1,2,3,4,5 ...
- All these parts are randomly present in an input buffer:
B1, C5, D2,A4,A2, etc
The aim now is to sort all parts into their collections, and make sure that in each collection the parts are ordered correctly.
A desired output would be: A1,A2,A3,A4,A5 B1,B2,B3,B4,B5, ..etc
This will be a physical process in which the parts are sheets of material. This gives some real world constraints:
- A sorting and output buffer of Nb locations is available.
- On each of the buffer locations multiple sheets can be stacked.
- To retrieve one particular sheet, all sheets that are placed on top of it need to be moved (and temporarily stored in another location). This takes physical effort + time and should therefor be minimized.
- It is not possible to move a correctly ordered subset of a collection at once. This would involve picking up each sheet individually from it's stack.
- Once a collection is completely sorted and ordered, it can be removed from the buffer.
The question: I am getting to grips with the logic of this sorting and ordering problem. Some initial questions I have asked myself, and you might find interesting to think about/test/simulate.
- For a given input (N, n) what is an efficient number of buffer locations (Nb)?
- What should be the sorting logic in this problem? Which rules would work when N scales to max. 30 and n to max. 150
- Does anyone have sources (papers, articles, algorithms, etc) on this type of problem?
- What aspect of the system should be changed to make the sorting more efficient? For instance what would be the benefit of being able to physically move a subset of a collection at once, while maintaining it's ordering.
I was struggling with clearly writing down the specifics of this sorting and ordering problem, if something is unclear, let me know so I can provide more info.