1
$\begingroup$

I have a collection of possibly repeated items that I need to map onto another set with possibly repeated items. I need to know an efficient algo to iterate through the unique mapping combinations. But first it would be great to know a formula to calculate the number of mappings upfront, before iteration.

E.g. when I need to map {A, B, B} onto {X, X, Y}, then unique mappings from destination collection point of view are:

X:ABB  X:     Y:
X:AB   X:B    Y: 
X:AB   X:     Y:B
X:A    X:BB   Y:
X:A    X:B    Y:B
X:A    X:     Y:BB
X:BB   X:     Y:A
X:B    X:B    Y:A
X:B    X:     Y:AB
X:     X:     Y:ABB
$\endgroup$
  • $\begingroup$ Does the number of elements in $\{A,B,B\}$ always match the number of elements in $\{X,X,Y\}$? $\endgroup$ – user334732 Jun 16 '16 at 7:46
  • $\begingroup$ No. Other example: {A,B,B,B,C,C} onto {X,X,Y,Z}. Typically the first collection is much larger in size. $\endgroup$ – pfp.meijers Jun 16 '16 at 7:57
  • $\begingroup$ Is $\emptyset, ABC$ definitely different to $ABC,\emptyset$? $\endgroup$ – user334732 Jun 16 '16 at 8:07
  • $\begingroup$ This is a difficult partitioning problem. The theory is here: en.wikipedia.org/wiki/Partition_(number_theory). You must first create a set X containing enumerations of each distinct character in $\{A,B,B\}$ so in your example this is $\{1,2\}$. Then you must enumerate the $distinct$ partitions of that set into $m$ or fewer parts, where $m$ is the number of elements in your 2nd set. This is done by summing for every partition up to and including $m$. Finally, you need to enumerate how many ways those parts can be distributed among the number of destinations available -in this case 3. $\endgroup$ – user334732 Jun 16 '16 at 8:38
  • $\begingroup$ This method is necessary because you may have multiple empty sets in different positions, and also the orders of the elements in their ultimate destinations matter. $\endgroup$ – user334732 Jun 16 '16 at 8:49
1
$\begingroup$

Inspired by the comments from Robert Frost I came up with following algo:

Create groups of identical source elements.
  Example: {{B,B},{A}}

Start with "empty" (unmapped) destination elements.
  Example: {X:-, Y:-, X:-}  
    (Initially destination elements are unordered. 
    And for a to be determined mapping the order does not matter.) 

Recursively loop through the source groups, and for such a group do the following:

    Create an ordered list of destination elements. 
    Ordering is based on element type and mapped source elements.
    Hence X:- is different from X:BB, but two elements X:B are equal.
        Examples:
            {X:-, X:-, Y:}   
            {Y:-, X:B, X:B}  
            {X:BB, Y:A, X:-}
            Note that {X:B, Y:-, X:B} is not a valid example.

    Use a "shifting" algorithm to iterate through all unique mappings 
    of the source group elements onto the destination elements:   

        Start with all source elements mapped onto the first destination element. 
            Example: {X:BB, X:-, Y:-}

        Start with a shift position at the first destination element. 
            Example: {<X>:BB, X:-, Y:-} 
                where <.> indicates the destination element from which a source element 
                will be shifted (remapped) next.        

        Loop until no shift is possible:

            If there is a next source element group, then map this recursively. 
            Else yield the mapping.

            Shift (remap) a source element of current (group) type at the current 
            shift position towards the next -different- destination position. 
                Examples: 
                    {<X>:BB, X:-, Y:-} => {X:B, X:B, Y:- } 
                    {<X>:B,  X:-, Y:B} => {X:-, X:-, Y:BB} 
                        (2nd position X is skipped because that does not yield a 
                        different mapping)  

            If there is no such different position, 
            then reset the shift position to the first destination element.
                Example: {X:B, <X>:B, Y:-} => {<X>:B, X:-, Y:B} 
                    (B from 2nd X is shifted to the Y, 
                    and next shift position reset to first X)

            If the first destination element has no source element of current type, 
            then shifting is no longer possible.
                Example: {<X>:B, X:-, Y:B} => {<X>:-, X:-, Y:BB} (done)

To be tested. Comments/suggestions are welcome.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.