# How can I convert sequences to sharings and vice versa?

Given positive integers $$k,n$$, a $$k$$-sequence of $$I_n$$ is a list of $$k$$ not necessarily distinct elements of $$\{1,\dots, n\}$$. And an $$n$$-sharing of $$I_k$$ is a list of $$n$$ possibly empty, disjoint subsets of $$\{1,\dots, k\}$$ that union up to $$\{1,\dots, k\}$$. There is a one-to-one correspondence between the $$k$$-sequences of $$I_n$$ and the $$n$$-sharings of $$I_k$$, where the $$i$$th element of the sharing contains all indices $$j$$ of the sequence that store the number $$i$$. For example, the $$3$$-sequence $$(4, 1, 1)$$ of $$I_4$$ is mapped to the $$4$$-sharing $$(\{2,3\}, \varnothing, \varnothing, \{1\})$$ of $$I_3$$ because the two indices storing a $$1$$ in the sequence are $$2$$ and $$3$$, the only index in the sequence storing a $$4$$ is $$1$$, and there are no indices storing $$2$$ or $$3$$. How can I convert between $$k-$$sequences of $$I_n$$ and $$n$$-sharings of $$I_k$$ in mathematica?

Looks like a case for PositionIndex:

ClearAll[toPositions]
toPositions = PositionIndex[#] /@ Range[Max@#] /. _Missing -> {} &;


Examples:

toPositions @ {4, 1, 1}

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

toPositions @ {5, 2, 3, 2, 5, 3, 5, 5}

{{}, {2, 4}, {3, 6}, {}, {1, 5, 7, 8}}


To recover the input list from positions:

ClearAll[fromPositions]
fromPositions = Values @* KeySort @*
KeyValueMap[Sequence @@ Thread[List /@ # -> First@#2] &]
@* KeyDrop[{{}}] @* PositionIndex;


Examples:

fromPositions@{{2, 3}, {}, {}, {1}}

 {4, 1, 1}

fromPositions@{{}, {2, 4}, {3, 6}, {}, {1, 5, 7, 8}}

 {5, 2, 3, 2, 5, 3, 5, 5}

SeedRandom
list = RandomChoice[Range@6, 10]

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

toPositions@list

{{4, 6, 7, 9, 10}, {5}, {2, 8}, {}, {1, 3}}

fromPositions @ %

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

SeedRandom
lists = RandomChoice[Range@7, {100, 20}];

AllTrue[fromPositions@toPositions@# == # &] @ lists

True

• Thank you for the great answer! Just one question: what's the underscore in front of Missing in the toPositions function? Is it like the wildcard in Ocaml? Feb 26, 2022 at 19:37
• @user236343, see Blank (_) in the documentation center.
– kglr
Feb 26, 2022 at 19:53