关于求解字符串排列函数perm的逆排列序列seq_c的技术问询

Great question! Let's break this down step by step—what you're looking for is the inverse permutation of seq, which will undo the original permutation and restore your original string.

First, Let's Clarify How perm Works #

From your examples, we know that for perm(in, seq):

• The output string out follows out[i] = in[seq[i]] (where seq[i] is the integer value of the character at position i in seq).
• In plain terms: the i-th character of the result comes from the seq[i]-th character of the input.

What Does seq_c Need to Do? #

We need perm(perm(str, seq), seq_c) == str. Let's translate this into index logic to make it clear:

1. Let s = perm(str, seq), so s[i] = str[seq[i]] for all positions i.
2. Applying perm again with seq_c gives: perm(s, seq_c)[j] = s[seq_c[j]] = str[seq[seq_c[j]]].
3. For this to equal str[j] (the original character at position j), we need seq[seq_c[j]] = j for every j.

This is exactly the definition of an inverse permutation: seq_c[j] is the index k where seq[k] = j.

Step-by-Step to Construct seq_c #

Let's use your examples to make this concrete:

Example 1: seq = "201"

1. Convert seq to a numeric array: perm_arr = [2, 0, 1]
2. Create an empty inverse array inv_perm_arr of the same length.
3. For each target index j (0, 1, 2):
   • Find k where perm_arr[k] = j:
     • j=0: perm_arr[1] = 0 → inv_perm_arr[0] = 1
     • j=1: perm_arr[2] = 1 → inv_perm_arr[1] = 2
     • j=2: perm_arr[0] = 2 → inv_perm_arr[2] = 0
4. Convert inv_perm_arr back to a string: seq_c = "120"

Verification:

• perm("abc", "201") = "cab"
• perm("cab", "120") → out[0] = cab[1] = 'a', out[1] = cab[2] = 'b', out[2] = cab[0] = 'c' → "abc" (matches the original string!)

Example 2: seq = "210"

1. Numeric array: perm_arr = [2, 1, 0]
2. Build inverse array:
   • j=0: perm_arr[2] =0 → inv_perm_arr[0] =2
   • j=1: perm_arr[1] =1 → inv_perm_arr[1] =1
   • j=2: perm_arr[0] =2 → inv_perm_arr[2] =0
3. String result: seq_c = "210"

Verification:

• perm("abc", "210") = "cba"
• perm("cba", "210") = "abc" (perfect, it undoes itself!)

General Algorithm #

To create seq_c from any valid seq:

• Convert seq into an array of integers (let's call this p).
• Initialize an array inv_p of the same length as p.
• For each index k from 0 to len(p)-1:
  • Set inv_p[p[k]] = k (because p[k] is the original index mapped to position k, so the inverse maps p[k] back to k).
• Convert inv_p back to a string (each integer becomes a character) to get seq_c.

This works because permutations are bijections (one-to-one and onto mappings), so every value in p has exactly one corresponding index k—no duplicates or missing values.

内容的提问来源于stack exchange，提问作者lsund