Motivation
GROUPING BY SWAPPING (P169) from Garey & Johnson, A4 SR21. A classical NP-complete problem concerning the minimum number of adjacent symbol interchanges needed to rearrange a string so that all occurrences of each symbol form a single contiguous block. This is closely related to sorting problems and token swapping on graphs.
Associated reduction rules:
- R115: FEEDBACK EDGE SET -> GROUPING BY SWAPPING (this is the GJ reference reduction)
Definition
Name: GroupingBySwapping
Canonical name: Grouping by Swapping (also: Block Sorting by Adjacent Transpositions)
Reference: Garey & Johnson, Computers and Intractability, A4 SR21
Mathematical definition:
INSTANCE: Finite alphabet Sigma, string x in Sigma*, and a positive integer K.
QUESTION: Is there a sequence of K or fewer adjacent symbol interchanges that converts x into a string y in which all occurrences of each symbol a in Sigma are in a single block, i.e., y has no subsequences of the form aba for a,b in Sigma and a != b?
The problem is a decision (satisfaction) problem: the answer is YES or NO depending on whether x can be grouped with at most K adjacent swaps.
Variables
- Count: K (the budget), one variable per swap slot.
- Per-variable domain: Each variable takes a value in {0, 1, ..., string_len - 1}. Values 0 through string_len - 2 represent swapping positions i and i+1. The value string_len - 1 is a no-op (identity), allowing sequences shorter than K.
- Meaning: A configuration [i_1, i_2, ..., i_K] represents applying adjacent swaps sequentially: first swap positions i_1 and i_1+1, then i_2 and i_2+1, etc. (no-ops are skipped). The configuration is satisfying if the resulting string has all occurrences of each symbol contiguous.
- dims():
vec![string_len; budget]
- evaluate(): Apply the K swaps to the input string in order, then check if the result is grouped (no subsequence aba with a ≠ b). Returns
true if grouped, false otherwise.
Schema (data type)
Type name: GroupingBySwapping
Variants: none (no graph or weight type parameter; operates on strings over a finite alphabet)
| Field |
Type |
Description |
alphabet_size |
usize |
Size of the finite alphabet Sigma (symbols indexed 0..alphabet_size) |
string |
Vec<usize> |
The input string x, encoded as a sequence of symbol indices |
budget |
usize |
The budget K: maximum number of adjacent swaps allowed |
Complexity
- Decision complexity: NP-complete (Garey & Johnson, 1979, SR21; transformation from FEEDBACK EDGE SET).
- Best known exact algorithm: Brute-force enumeration of all swap sequences of length at most K. Each of the K slots chooses one of string_len - 1 swap positions, giving O(string_len^budget) configurations to check.
- Complexity expression:
"string_len ^ budget"
- Related tractable cases:
- For a 2-symbol alphabet (binary), the problem is equivalent to counting inversions between the two groups and is solvable in O(|x| log |x|) time.
- On special graph topologies (stars, complete graphs), the related token swapping problem is polynomial.
- Parameterized: The problem is fixed-parameter tractable when parameterized by the alphabet size |Sigma| (since the number of possible block orderings is |Sigma|!, and for each ordering the minimum swaps can be computed).
- References:
- [Garey & Johnson, 1979] M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman, 1979, problem SR21.
- [Bonnet et al., 2018] E. Bonnet et al., "Complexity of Token Swapping and Its Variants", Algorithmica 80(9), pp. 2656-2682.
Extra Remark
Full book text:
INSTANCE: Finite alphabet Sigma, string x in Sigma*, and a positive integer K.
QUESTION: Is there a sequence of K or fewer adjacent symbol interchanges that converts x into a string y in which all occurrences of each symbol a in Sigma are in a single block, i.e., y has no subsequences of the form aba for a,b in Sigma and a != b?
Reference: [Howell, 1977]. Transformation from FEEDBACK EDGE SET.
How to solve
Example Instance
Alphabet Sigma = {a, b, c} (alphabet_size = 3)
String x = "abcabc" (length 6)
Budget K = 5
Symbol positions in x:
- a: positions 0, 3
- b: positions 1, 4
- c: positions 2, 5
Target: group all symbols into contiguous blocks.
There are 3! = 6 possible block orderings. The nearest is "aabbcc".
Step-by-step solution (3 adjacent swaps):
| Step |
Swap |
Result |
| 0 |
— |
a b c a b c |
| 1 |
swap(2,3): c↔a |
a b a c b c |
| 2 |
swap(1,2): b↔a |
a a b c b c |
| 3 |
swap(3,4): c↔b |
a a b b c c |
Total: 3 swaps. Since 3 ≤ 5 = K, the answer is YES.
Expected Outcome
The minimum number of adjacent swaps to group "abcabc" is 3. No sequence of 2 or fewer swaps can group this string, since at least 3 crossings must be resolved (a at position 3 crosses b at 1 and c at 2; b at position 4 crosses c at 2).
The 3-swap sequence above produces "aabbcc". Other grouped permutations reachable within K = 5 swaps include "bbaacc" (5 swaps) and "aaccbb" (5 swaps). Out of 90 distinct permutations of "abcabc", exactly 6 are grouped.
Satisfying configuration: [2, 1, 3, 5, 5] — swap positions 2, 1, 3 followed by two no-ops (5 = string_len - 1).
Motivation
GROUPING BY SWAPPING (P169) from Garey & Johnson, A4 SR21. A classical NP-complete problem concerning the minimum number of adjacent symbol interchanges needed to rearrange a string so that all occurrences of each symbol form a single contiguous block. This is closely related to sorting problems and token swapping on graphs.
Associated reduction rules:
Definition
Name:
GroupingBySwappingCanonical name: Grouping by Swapping (also: Block Sorting by Adjacent Transpositions)
Reference: Garey & Johnson, Computers and Intractability, A4 SR21
Mathematical definition:
INSTANCE: Finite alphabet Sigma, string x in Sigma*, and a positive integer K.
QUESTION: Is there a sequence of K or fewer adjacent symbol interchanges that converts x into a string y in which all occurrences of each symbol a in Sigma are in a single block, i.e., y has no subsequences of the form aba for a,b in Sigma and a != b?
The problem is a decision (satisfaction) problem: the answer is YES or NO depending on whether x can be grouped with at most K adjacent swaps.
Variables
vec![string_len; budget]trueif grouped,falseotherwise.Schema (data type)
Type name:
GroupingBySwappingVariants: none (no graph or weight type parameter; operates on strings over a finite alphabet)
alphabet_sizeusizestringVec<usize>budgetusizeComplexity
"string_len ^ budget"Extra Remark
Full book text:
INSTANCE: Finite alphabet Sigma, string x in Sigma*, and a positive integer K.
QUESTION: Is there a sequence of K or fewer adjacent symbol interchanges that converts x into a string y in which all occurrences of each symbol a in Sigma are in a single block, i.e., y has no subsequences of the form aba for a,b in Sigma and a != b?
Reference: [Howell, 1977]. Transformation from FEEDBACK EDGE SET.
How to solve
Example Instance
Alphabet Sigma = {a, b, c} (alphabet_size = 3)
String x = "abcabc" (length 6)
Budget K = 5
Symbol positions in x:
Target: group all symbols into contiguous blocks.
There are 3! = 6 possible block orderings. The nearest is "aabbcc".
Step-by-step solution (3 adjacent swaps):
Total: 3 swaps. Since 3 ≤ 5 = K, the answer is YES.
Expected Outcome
The minimum number of adjacent swaps to group "abcabc" is 3. No sequence of 2 or fewer swaps can group this string, since at least 3 crossings must be resolved (a at position 3 crosses b at 1 and c at 2; b at position 4 crosses c at 2).
The 3-swap sequence above produces "aabbcc". Other grouped permutations reachable within K = 5 swaps include "bbaacc" (5 swaps) and "aaccbb" (5 swaps). Out of 90 distinct permutations of "abcabc", exactly 6 are grouped.
Satisfying configuration: [2, 1, 3, 5, 5] — swap positions 2, 1, 3 followed by two no-ops (5 = string_len - 1).