# How to get the all the lists of preimages of a surjective map is the image is given?

Firstly, I want to construct a map with the preimage {{5}, {4, 3}, {4, 2}, {3, 2, 1}, {2, 2, 1}, {2, 1}} and the image {1, 1, 2, 2, 3, 4} correspondingly. So as you can see it's a surjective map.

Then, I hope to have a function that if we input {1,2,3},

I will get all possible combinations of their corresponding preimages, i.e. {{5}, {4, 2}, {2, 2, 1}}, {{5}, {3, 2, 1}, {2, 2, 1}}, {{4, 3}, {4, 2}, {2, 2, 1}}, {{4, 3}, {3, 2, 1}, {2, 2, 1}}.

The order of the lists is not important, but inside each list, the order should be kept.

Could you offer me some help?

ClearAll[f]
f[pi_, im_] := Tuples @* Map[GroupBy[AssociationThread[pi, im]] @ pi]


Examples:

pimg = {{5}, {4, 3}, {4, 2}, {3, 2, 1}, {2, 2, 1}, {2, 1}};
img = {1, 1, 2, 2, 3, 4};

f[pimg , img] @ {1, 2, 3}

 {{{5}, {4, 2}, {2, 2, 1}},
{{5}, {3, 2, 1}, {2, 2, 1}},
{{4, 3}, {4, 2}, {2, 2, 1}},
{{4, 3}, {3, 2, 1}, {2, 2, 1}}}

f[pimg , img] @ {1, 2}

{{{5}, {4, 2}},
{{5}, {3, 2, 1}},
{{4, 3}, {4, 2}},
{{4, 3}, {3, 2, 1}}}

f[pimg , img] @ {3, 2}

{{{2, 2, 1}, {4, 2}},
{{2, 2, 1}, {3, 2, 1}}}


Alternatively, you can construct a list of Associations from pimg and img and use Merge:

ClearAll[g]
g[pi_, im_] := Tuples @* Map[Merge[Identity][Association /@ Thread[im -> pi]]]

g[pimg, img] == f[pimg, img]

True


One way to represent the function, call it map, is like this

domain = {{5}, {4, 3}, {4, 2}, {3, 2, 1}, {2, 2, 1}, {2, 1}};
image = {1, 1, 2, 2, 3, 4};

map = Transpose[{domain, image}];


To find the preimage of a subset, img, of the image set, do this

img = {1, 2, 3};
preimage = First /@ Select[map, MemberQ[img, Last[#]] &] // DeleteDuplicates

{{5}, {4, 3}, {4, 2}, {3, 2, 1}, {2, 2, 1}}


or this

preimage = Select[map, MemberQ[img, Last[#]] &] // Transpose // First // Union

{{5}, {4, 2}, {4, 3}, {2, 2, 1}, {3, 2, 1}}


Note that using DeleteDuplicates as in the first example gives an unsorted preimage and using Union as in the second example gives a sorted preimage.

Another way to define the mapping is with an association. Finding the preimage is then a matter of using Position to find the "keys" of the association that map to the "values" in the image, like this

map2 = Association[Rule @@@ map];
keys = Position[map2, #] & /@ img // Flatten;
preimage = keys /. Key -> Identity

{{5}, {4, 3}, {4, 2}, {3, 2, 1}, {2, 2, 1}}


make a defaultdict

ass=AssociationMap[Function[x,{}] , {1, 1, 2, 2, 3, 4}];


groupby it

MapThread[AppendTo[ass[#1],#2]&,
{
{1, 1, 2, 2, 3, 4},
{{5}, {4, 3}, {4, 2}, {3, 2, 1}, {2, 2, 1}, {2, 1}}
}
];


then

Tuples[ass/@{1,2,3}]


will give us all we need,