Computing a map between two lists

What I want is a little difficult to explain. So I try to it with an example.

I have 2 lists, each of which has $(n-1)^2$ elements. Each element is an integer between 0 and $n-1$, inclusive.

For example for $n=4$:

L1 = {1,2,3,2,0,2,3,2,1}
L2 = {2,3,0,3,0,1,0,1,2}

From these lists I want to compute possible elements of L2 that correspond to an element of L1. The result is an ordered list with $n$ elements:

{{0},{2},{1,3},{0}}

This means:

• If you select 0 from L1, the corresponding elements in L2 are {0}.
• If you select 1 from L1, the corresponding elements in L2 are {2}.
• If you select 2 from L1, the corresponding elements in L2 are {1,3}.
• If you select 3 from L1, the corresponding elements in L2 are {0}.
• for n=3 max element must be 2? In your exmaple L1:={1,2,3,2,0,2,3,2,1} with n=3max element is 3. – molekyla777 Oct 31 '14 at 8:18
• Thank you. I corrected the typo. – user21814 Oct 31 '14 at 8:20
• Does L1 always contains whole range 0 to n-1? – Kuba Oct 31 '14 at 8:43
• Good question! No, it does not. Some of the result elements could very well be empty: {}. In particular, for $n$ a large prime, there could be many empty sets. – user21814 Oct 31 '14 at 8:50

GatherBy[Union@Transpose@{L1, L2}, First][[;; , ;; , 2]]
• Forget a day or 2. Good enough. Thank you. – user21814 Oct 31 '14 at 9:07
Sort@Thread[L1 -> L2] ~Merge~ Union // Values
{{0}, {2}, {1, 3}, {0}}

After reading Kuba's answer I realize this could also be written:

Values @ Merge[Union @ Thread[L1 -> L2], # &]
• This is a nice representation of the problem, especially (imo) without the Values, in which it actually is a mapping instead of the OP's stripped down representation of one. (+1) – Michael E2 Oct 31 '14 at 12:44

With MMA10 this can be done by this code:

DeleteDuplicates /@ GroupBy[Transpose@{L1, L2}, First -> Last]
(*<|1 -> {2}, 2 -> {3, 1}, 3 -> {0}, 0 -> {0}|>*)
n = 4;
(* {{0}, {2}, {1, 3}, {0}} *)

Faster than I thought it would be, but not as fast as Kuba's when L1 and L2 are packed arrays.

The graph itself is a nice representation of the problem.

You can also use Nearest for this purpose:

r = Union /@ Nearest[L1 -> L2, Range[0, 3]]

{{0}, {2}, {1, 3}, {0}}

A timing comparison with @Kuba's answer:

L1 = RandomInteger[1000,10^6];
L2 = RandomInteger[1000,10^6];

r1 = GatherBy[Union @ Transpose@{L1,L2}, First][[;; , ;; , 2]]; //AbsoluteTiming
r2 = Union /@ Nearest[L1 -> L2, Range[0, 1000]]; //AbsoluteTiming

r1===r2

{0.299931, Null}

{0.191812, Null}

True

So, a little bit faster.

Another approach:

Values[KeySort[Merge[Thread[L1 -> L2], Union]]]

Alternatively DeleteDuplicates could be used.

Union[Pick[L2, L1, #]] & /@ Range[0, 3]

{{0}, {2}, {1, 3}, {0}}
{"ft_lang_label":"__label__en","ft_lang_prob":0.82002276,"math_prob":0.9749538,"size":1048,"snap":"2019-43-2019-47","text_gpt3_token_len":394,"char_repetition_ratio":0.13697319,"word_repetition_ratio":0.09189189,"special_character_ratio":0.39026716,"punctuation_ratio":0.21323529,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9684301,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-19T18:38:45Z\",\"WARC-Record-ID\":\"<urn:uuid:2744912e-e45a-4888-a38c-1d6e02dc140a>\",\"Content-Length\":\"177855\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:07048386-9b0c-4645-9267-7ecd33f23324>\",\"WARC-Concurrent-To\":\"<urn:uuid:0d494b81-e60e-4754-9c69-40f9852545a6>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://mathematica.stackexchange.com/questions/64559/computing-a-map-between-two-lists\",\"WARC-Payload-Digest\":\"sha1:LXRLKGSQCFU7DH33PVXUQL32SLRPKNAH\",\"WARC-Block-Digest\":\"sha1:JOUWA34SGC4R7ISQR2VDHA45TH4D66YW\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570986697439.41_warc_CC-MAIN-20191019164943-20191019192443-00456.warc.gz\"}"}