该算法是否会被视为最小变化算法？

发布于 2024-12-19 11:43:00 字数 1250 浏览 0 评论 0原文

对于我的算法课，我们需要编写一个自下而上的最小变化算法。

作为示例输出，我们的教授向我们提供了

n=4
1234     2314     3124
1243     2341     3142
1423     2431     3412
4123     4231     4312
4132     4213     4321
1432     2413     3421
1342     2143     3241
1324     2134     3214

通知，它生成 24 种排列（每个数字 6 种排列）。 4 的排列（例如，4 是排列中的第一个数字）是该算法中其他调用的副产品。您还可以看到，每次切换位置最多只有 2 个数字。

我一直在努力在这些数字中找到一个好的模式来作为我的代码的基础。所以我正在考虑采取稍微不同的方法来解决这个问题。

如果我取 n 的阶乘，我可以计算排列的数量。通过将排列数除以n，我得到每个数字在每个相应位置的次数（即每个数字开始的排列数）。将后续结果除以 n-1，在第一个数字保持不变的情况下，我得到第二个数字出现的次数。依此类推（n每次减一），直到用完所有数字。

例如，假设 n=4

4! = 24
24/4 = 6
6/3 = 2
2/2 = 1

使用这些结果我可以生成垂直排列，而不是水平排列。

相反，我会生成一个维度为 nxn! 的表格，而不是获取一个数字并在其他数字上来回滑动并经常进行交换。然后，沿着各列向下填写第一列，其中包含 6 个一、6 个二、6 个三、6 个四和 6 个五。

当我到达第二列时，每个数字将被放入两次，然后重复直到到达数组末尾。随后，每一列都会遵循类似的模式。此模式适用于任何大小的 n 输入。

我的输出是这样的：

n=4
1234    2134    3124    4123
1243    2143    3142    4132
1324    2314    3214    4213
1342    2341    3241    4231
1423    2413    3421    4312
1432    2431    3412    4321

现在我的问题是......这仍然被认为是最小变化算法吗？

我的算法更多地按字典顺序工作，这让我担心它可能不会被视为最小变化算法（因为在某些步骤中，多个数字似乎被“交换”，尽管实际上没有进行交换）。

原文

For my algorithms class we are required to write a bottoms-up minimal-change algorithm.

As an example output our professor provided us with

n=4
1234     2314     3124
1243     2341     3142
1423     2431     3412
4123     4231     4312
4132     4213     4321
1432     2413     3421
1342     2143     3241
1324     2134     3214

Notice that it generates 24 permutations (6 for each digit). The permutations for 4 (as in, 4 being the first number in a permutation) are a byproduct from the other calls in that algorithm. You can also see that at most only 2 numbers every switch positions.

I've been struggling to find a good pattern within those numbers to base my code on.
So I was thinking of taking a slightly different approach to the problem.

If I take the factorial of n I can calculate the number of permutations. By dividing the number of permutations by n I get the number of times each digit is in each respective position (i.e. how many permutations start with each number). Dividing the subsequent result by n-1 I get the number of times each second digit will occur, given the first digit remains the same. So on and so forth (with n being decreased by one every time) until all digits have been exhausted.

As an example, assume that n=4

4! = 24
24/4 = 6
6/3 = 2
2/2 = 1

Using these results I can generate permutations vertically, not horizontally.

Instead taking a number and sliding it back and forth over the other numbers and doing swaps every so often I would instead generate a table that is nxn! in dimension. Then, going down the columns fill in the first column with 6 ones, 6 twos, 6 threes, 6 fours, and 6 fives.

When I get to second column each number would be put in twp times, and then repeated until the end of the array is reached. Subsequently, each column would follow a similar pattern. This pattern would work with any sized n input.

My output would be this:

n=4
1234    2134    3124    4123
1243    2143    3142    4132
1324    2314    3214    4213
1342    2341    3241    4231
1423    2413    3421    4312
1432    2431    3412    4321

Now my question is... is this still considered a minimal-change algorithm?

My algorithm works more in lexicographical order, and that worries me that it may not be considered a minimal-change algorithm (because during certain steps more than one number seems 'swapped', though in reality no swapping is being done).

分享到QQ

分享到微博