Excel-确定排列的奇偶性 [英] Excel - Determine Parity of Permutation

问题描述

我正在处理Excel工作表，需要确定大小为 N 的垂直数字数组的奇偶校验.数组包含从 1 到 N 的每个数字，每个数字恰好一次.

I am working on an Excel sheet where I need to determine the parity of a vertical array of numbers of size N. The array contains each number from 1 to N exactly one time each.

在这种情况下，奇偶校验定义为将加扰后的数组从最小数组转换为最大数组所需的交换次数.

In this context, parity is defined as how many swaps is necessary to convert the scrambled array to a sorted array from smallest to largest.

例如，数组{3;1;2;4}具有奇偶校验，因为它需要两次交换(至少)才能转换为{1;2;3;4}，但始终需要偶数交换.见下文.

For example, the array {3;1;2;4} has even parity because it would require two swaps (at minimum) to convert to {1;2;3;4}, but would always require an even number of swaps. See below.

3   -->   1         1
1   -->   3   -->   2
2         2   -->   3
4         4         4

另一个示例:{2;1;4;5;3}具有奇数奇偶校验，因为它至少需要进行三个交换才能转换为{1;2;3;4;5}，但始终需要奇数个交换.见下文.

Another example: {2;1;4;5;3} has odd parity because it would require three swaps (at minimum) to convert to {1;2;3;4;5}, but would always require an odd number of swaps. See below.

2   -->   1         1         1
1   -->   2         2         2
4         4   -->   3         3
5         5         5   -->   4
3         3   -->   4   -->   5

我正在寻找一种解决方案，对于奇偶校验的数组将返回TRUE，对于奇偶校验的数组将返回FALSE. (而且我不在乎不包含从 1 到 N 的所有数字的数组的结果是什么，因为电子表格中还有其他检查方法可以处理这些情况. )

I am looking for a solution that would return TRUE for arrays with even parity and FALSE for arrays with odd parity. (And I don't care what the result is for arrays that do not contain all numbers from 1 to N because I have other checks in the spreadsheet to handle those cases.)

我想出了一个使用多个帮助器列的解决方案，但是这似乎是一种缓慢的计算.

I have figured out a solution that uses several helper columns, but it seems like a sluggish calculation.

我通过检查数组中的每个数字是否在正确的索引中以及是否不执行交换来实现此目的.然后，我总结发生的掉期数量，并使用MOD(<swaps>,2)=0来确定它是否是偶数.

I do this by checking if each individual number in the array is in the correct index and, if it isn't perform a swap. I then sum up the amount of swaps that occurred and use MOD(<swaps>,2)=0 to determine if it is even parity.

有关使用数组{8;5;3;2;4;1;7;6}的示例计算，请参见下文.

See below for an example calculation with the array {8;5;3;2;4;1;7;6}.

我已经对单元格进行了颜色编码，以轻松判断正在发生的事情:

I've color coded the cells to easily tell what is happening:

白色=参考数组{1;2;3;4;5;6;7;8}

蓝色=输入数组

Grey ="helper"数组，其中每个连续的列在必要时执行交换

Grey = "helper" arrays where each successive column performs a swap if necessary

红色=表示是否与上一列发生了交换

Red = Indicates if a swap occurred from previous column

如果该列中发生了交换，则绿色= 1，如果未发生交换，则为0

Green = 1 if swap occurred in that column, and 0 if a swap didn't occur

黄色=所有绿色单元格的总和，有效地表明发生了多少次交换.

Yellow = Sum of all green cells, effectively telling how many swaps occurred.

在此示例中，由于黄色单元格为4(偶数)，因此输入数组具有奇偶校验.

In this example, since the yellow cell is 4, which is an even number, the input array has even parity.

问题是:在没有VBA的情况下，可以在Excel中更有效地完成此计算吗?我不一定要反对辅助专栏，但同样，我的解决方案似乎呆滞，我想知道是否有更好的方法.

The question is: Can this calculation be done more efficiently in Excel without VBA? I'm not necessarily against helper columns, but again it just seems that my solution is sluggish and I'm wondering if there is a better way.

推荐答案

我想我有一种无需帮助者列的方法！

I think I have a way of doing this without the helper columns!

首先，我将通过 N 帮助器列向您展示一种方法，然后将向您展示如何使用数组公式.考虑下面显示的矩阵:

First, I'll show you a way with N helper columns and then I'll show how to use array formulas instead. Consider the matrix show below:

绿色范围是索引，蓝色范围是您的排列.黄色矩阵是您的排列矩阵，如公式框中所示.

The green ranges are the indices and the blue range is your permutation. The yellow matrix is your permutation matrix defined as seen in the formula box.

排列的奇偶校验与该矩阵的行列式的值相同！

幸运的是，Excel具有内置的行列式函数MDETERM().偶数排列的奇偶性为1，奇数排列的奇偶性为-1，因此您可以使用公式简单地获取行列式

Luckily, Excel has a built-in determinant function MDETERM(). An even permutation has parity 1 and an odd permutation has parity -1, so you can get the determinant simply with the formula

=MDETERM(C2:J9)

现在这很酷，但真正的关键是我们甚至不需要制作该矩阵.我们可以将其构造为如下所示的数组公式:

Now this is pretty cool, but the real kicker is that we don't even need to make that matrix. We can construct it in an array formula like this instead:

{=MDETERM(IF(B2:B9=TRANSPOSE(A2:A9),1,0))}

在这里，我们仅使用列A和B！在此版本中，C:J列未使用.

Here we only use columns A and B! Columns C:J are unused in this version.

(请注意，这是一个数组公式，因此您需要使用Ctrl + Shift + Enter进行验证.这会将括号括在公式中.请勿手动执行.)

(Note that this is an array formula so you will need to use Ctrl+Shift+Enter to validate it. This will wrap the braces around the formula. Don't do that manually.)

这篇关于Excel-确定排列的奇偶性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！