这个“词典顺序生成算法”是如何实现的？工作？

发布于 2024-08-05 08:40:01 字数 681 浏览 1 评论 0原文

词典顺序生成

对于每个数字 k，0 ≤ k < ！，以下算法生成相应的词典初始序列的排列 sj，j = 1，...，n：

函数排列(k, s) {
     var int n:= 长度(s);阶乘：= 1；
     for j= 2 到 n- 1 { // 计算 (n- 1)！
         阶乘：=阶乘* j；
     }
     对于 j= 1 到 n- 1 {
         tempj:= (k/阶乘) mod (n+ 1- j);
         临时:= s[j+临时j]
         对于 i= j+ tempj 到 j+ 1 步骤 -1 {
             s[i]:= s[i-1]; // 将链右移
         }
         s[j]:= 时间；
         阶乘：=阶乘/(n-j)；
     }
     返回 s；
 }

这背后的逻辑是什么？ 它是如何工作的？

原文

from Wikipedia:

Lexicographical order generation

For every number k, with 0 ≤ k < n!,
the following algorithm generates the
corresponding lexicographical
permutation of the initial sequence
sj, j = 1, ..., n:

function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

What is the logic behind this? How does it work??

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

月依秋水 2024-08-12 08:40:01

考虑一个多维数组，其中包含 n 个项目的所有排列，其维度为：

p[n][n-1][n-2]...[1]

任何多维数组可以线性化为维度为 1 的一维数组：

a[n*(n-1)*(n-2)*...*1]

这就像一个可变基数；按数值顺序确实可以为您提供数字的字典顺序。

用于引用元组 x[n] = 例如 (i[n],i[n-1]...,i[0]) 的索引是 sum_j i[ j]*(j!)

因此，除法/取模正在从元组中恢复下一个位置。

元组中第 k 个索引的值是其右侧维度的乘积，恰好是 k!。

回复收藏 0 原文

没有你我更好 2024-08-12 08:40:01

假设您有一个整数 x，并且您想知道百位上的数字是多少。（例如，如果 x=4723，您想要答案 7。）要计算此值，您首先除以 100，丢弃小数部分。（在我们的示例中，剩下 47。）然后求除以 10 时的余数。

现在假设您要求千位数的值。要找到这个结果，首先要除以 1000，去掉小数部分，然后再除以 10 求余数。

在常规十进制计数系统中，每个位置保存 10 个值之一。您可以观察到，在我们的数字查找练习中，我们首先除以我们关心的右侧位置的可能值组合的数量（第一个示例中为 10 * 10）。然后，我们除以我们关心的地方的可能值的数量，得到余数。当然，所有位置都有 10 个可能的值，因此我们只需除以 10。

现在，想象一个编号系统，其中每个位置保存不同数量的值。最右边的位置可以有两个值，0 或 1。下一个位置可以有三个值，0、1 或 2；等等。在这个系统中，我们这样计数：

这就是 wrang-wrang 所说的“可变基数”。

现在，您可以看到我们如何计算系统中某个位置的数字。要找到最右边的数字，我们不需要先除，而是找到模 2 的余数，因为该列中的数字有 2 个可能的值。为了找到左边的下一列，我们首先除以右边列中数字的可能组合数：只有一列有两个可能的数字，所以我们除以 2。然后我们取余数模 3，因为该列有三个可能的值。继续向左，对于第三列，我们除以 6（因为右边的列各有 3 种和 2 种可能性，相乘得到 6），然后取余数模 4，因为该列中有 4 个可能的值。

让我们看一下这个函数：

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorial 开头为 (n-1)！

    for j= 1 to n- 1 {

每次我们到达这里时，阶乘都等于(nj)！这在第一次时很明显，因为 j=1 并且我们知道我们将 factorial 初始化为 (n-1)！稍后我们会看到阶乘确实总是 (nj)！

        tempj:= (k/ factorial) mod (n+ 1- j);

在这里，我们将 k 除以阶乘（等于 (nj)！）并丢弃余数，然后将结果除以 (n+ 1-j）。等一下，我开始说的那些胡言乱语开始听起来很熟悉！我们只是使用我们的“可变基数系统”找到左起第 n 列中“数字”的值！

下一位采用索引 j 和 j + tempj 之间的元素序列并将其向右旋转 - 即每个元素都向上移动一个索引，除了最后一个元素向后移动到开始。重要的是要认识到位置 j 右侧的所有数字都是有序的。我们有效地把其中一个拔出来，并推动其余的保持秩序。我们挑选哪一个取决于 tempj。当 tempj 为 0 时，我们选择最小的（实际上不需要做任何微调），当 tempj 等于 nj 时，我们选择最大的。

        temps:= s[j+ tempj]
        for i= j+ tempj to j+ 1 step -1 {
            s[i]:= s[i- 1];      // shift the chain right
        }
        s[j]:= temps;

接下来，（nj）！除以 (nj) 得到 (nj-1)！
如果您考虑一下，您应该会发现，这意味着当我们回到循环顶部且 j 增加 1 时，factorial 将再次等于 (新泽西州）！

        factorial:= factorial/ (n- j);
    }
    return s;
}

我希望这有一点帮助！

Imagine you have a whole number x and you want to know what digit is in the hundreds position. (E.g. if x=4723 you want the answer 7.) To calculate this, you first divide by 100, throwing away the fractional part. (In our example, this leaves 47.) Then find the remainder when you divide by 10.

Now suppose you want to find the value of the digit in the thousands position. To find that you'd first divide by 1000, throwing away the fractional part, then again find the remainder when you divide by 10.

In the regular decimal numbering system, each place holds one of 10 values. You can observe that in our digit-finding exercise we first divide by the number of possible combinations of values in places to the right of the one we care about (10 * 10 in the first example). Then we find the remainder when dividing by the number of possible values for the place we care about. Of course, all places have 10 possible values, so we just divide by 10.

Now, imagine a numbering system where each place holds a different number of values. Our right-most place can have two values, 0 or 1. The next place can have three values, 0, 1 or 2; and so on. In this system we count like this:

This is what wrang-wrang means by a "variable-base number".

Now, you can see how we calculate the digit in a place in this system. To find the right-most we don't need to divide first, and we find the remainder modulo 2, because there are 2 possible values for a digit in that column. To find the next column to the left, we first divide by the number of possible combinations for digits in the columns on the right: there's only one column with two possible digits, so we divide by 2. Then we take the remainder modulo 3, because there are three possible values for this column. Continuing left, for the 3rd column we divide by 6 (because the columns to the right have 3 and 2 possibilities each, multiplying to make 6) and then take the remainder modulo 4, because there are 4 possible values in this column.

Let's take a look at the function:

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorial starts as (n-1)!

    for j= 1 to n- 1 {

Each time we get here, factorial is equal to (n-j)! This is obvious the first time round, since j=1 and we know we initialized factorial to (n-1)! We'll see later that factorial is indeed always (n-j)!

        tempj:= (k/ factorial) mod (n+ 1- j);

Here we divide k by factorial (which is equal to (n-j)!) and throw away the remainder, then we take the remained when we divide the result by (n+1-j). Wait a minute, all that babble I started with is beginning to sound familiar! We are just finding the value of the "digit" in the nth column from the left using our "variable-base number system"!

This next bit takes the sequence of elements between indices j and j + tempj and rotates it rightward - i.e. every element moves up one index, except the last one, which moves back to the start. It's important to realise that all the numbers on the right of position j are in order. We're effectively plucking one of them out and nudging the rest along to keep them in order. Which one we pluck out depends on tempj. When tempj is 0, we pick the smallest (and actually don't need to do any nudging), when tempj is equal to n-j, we pick the largest.

        temps:= s[j+ tempj]
        for i= j+ tempj to j+ 1 step -1 {
            s[i]:= s[i- 1];      // shift the chain right
        }
        s[j]:= temps;

Next, (n-j)! divided by (n-j) gives (n-j-1)!
If you think about it, you should see that this means that when we get back to the top of the loop and j has incremented by one, factorial will once again equal (n-j)!

        factorial:= factorial/ (n- j);
    }
    return s;
}

I hope that helps a bit!

回复收藏 0 原文

彼岸花ソ最美的依靠 2024-08-12 08:40:01

假设 u 的初始序列为 a[] = { 1,2,3,4,5,6 }of n = 6;你想生成第 k 个烫发。
在我的地方有 1 个，你可以生成 5 个！（即（n-1）！）对剩余位置进行烫发。

1 ,.......

然后你改变 1 和 2，然后你可以再次生成 5！烫发。

2 ,.......

所以思路是给定k，我们需要求k的范围。我的意思是：
假设k是225，有多少个5！ k 有：245/5！ = 2
所以如果 k = 245，在我想要生成的排列中，第一名肯定是
3（即a[2]）（bcoz在进行2*5！= 240之后，我将交换1和3），我将拥有

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

这就是为什么在算法中，你做k/（n-1）！在第一次迭代中。
并得到余数k = k mod (n-1)!。这是 k 的新值，u 递归地对 (nj) 做同样的事情！在剩下的地方。

Say u have initial sequence as a[] = { 1,2,3,4,5,6 }of n = 6; and u want to generate kth perm.
With 1 on Ist place, u can generate 5! (i.e. (n-1)! ) perms with the remaining places.

1 ,.......

Then u xchange 1 and 2 and again u can again generate 5! perms.

2 ,.......

So the idea is given k, we need to find the extent of k. What I mean is:
say k is 225, how many 5! does k have: 245/5! = 2
So if k = 245, in the permutation that I want to generate, the first place is definitely
3 (i.e. a[2]) (bcoz after going 2*5! = 240 , I will xchange 1 and 3), I will have

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

that's why in the algo, u do k/(n-1)! in the first iteration.
And obtain remainder k = k mod (n-1)!. This is new value of k and u go recursively doing the same thing with (n-j)! on the remaining places.

回复收藏 0 原文

~没有更多了~