Order-Preserving Shuffle Operator $\prec\hspace{-0.6em}\odot$ — Exact Mathematical Realization:
- Definition 3.8 [PETRI25, p. 10]
- Section 3.1 [BPM25, p. 6]
Mathematical Definition
Let $\sigma_1, \dots, \sigma_n \in X^*$ be sequences over a set $X$ with $n \ge 2$, and let $\prec \;\in \mathcal{O}_n$ be a strict partial order. Let $I = \{(j, k) \mid 1 \le j \le n \wedge 1 \le k \le |\sigma_j|\}$ be the set of all indexed positions. The order-preserving shuffle operator $\prec\hspace{-0.6em}\odot(\sigma_1, \dots, \sigma_n)$ is defined as:
$$ \prec\hspace{-0.6em}\odot(\sigma_1, \dots, \sigma_n) = \left\{\sigma \in X^* \;\middle|\; \begin{aligned} &|\sigma| = |I| \;\wedge\; \exists f \in \mathcal{B}(I, \{1,\dots,|\sigma|\}) \text{ s.t. } \forall (j,k) \in I, \sigma(f(j,k)) = \sigma_j(k) \\ &\wedge \forall (j_1,k_1),(j_2,k_2) \in I, (j_1 \prec j_2 \vee (j_1=j_2 \wedge k_1 < k_2)) \implies f(j_1,k_1) < f(j_2,k_2) \end{aligned}\right\} $$
Summary
Functions
Computes the complete multiset/set of valid order-preserving interleavings $\prec\hspace{-0.6em}\odot(\sigma_1, \dots, \sigma_n)$.
Functions
@spec op_shuffle([[term()]], [{pos_integer(), pos_integer()}]) :: [[term()]]
Computes the complete multiset/set of valid order-preserving interleavings $\prec\hspace{-0.6em}\odot(\sigma_1, \dots, \sigma_n)$.
Doctests [PETRI25 p. 10 Example]
iex> s1 = ["a", "b"]
iex> s2 = ["c"]
iex> s3 = ["d", "e"]
iex> poset = [{1, 2}, {1, 3}] # 1 ≺ 2 and 1 ≺ 3
iex> traces = Ex4pmEngine.POWL.Shuffle.op_shuffle([s1, s2, s3], poset)
iex> length(traces)
3
iex> ["a", "b", "c", "d", "e"] in traces
true
iex> ["a", "b", "d", "c", "e"] in traces
true
iex> ["a", "b", "d", "e", "c"] in traces
true