使用质数对每个集合元素进行编码。
例如:
a -> 2
b -> 3
c -> 5
现在,您需要再维护两个列表。
第一个列表是质数,第二个列表是它们的指数。
思路是:当您遇到一个元素时,记录它的质数和连续出现的次数。
对于[a, b, b, c]
,您会得到这个:
[2, 3, 3, 5]
这可以被记录为:
[2, 3^2, 5]
或者,更准确地说:
[2^1, 3^2, 5^1]
而且你维护两个列表:
[2,3,5] // primes in succession - list [p]
[1,2,1] // exponents - list [e]
现在,从两个列表的末尾到中间进行迭代,通过检查第一个元素 [p]^[e] 是否与最后一个元素相同来进行比较; 如果它们都相同,则依次检查第二个元素和倒数第二个元素等等... 如果它们全部都相同,则可以缩小列表。
在这个例子中,您要检查是否
2^1*5^1 == 3^2*3^2
; 由于它们不相同,因此无法缩小。
让我们尝试一下
[a, b, b, a, b, b]
:
这是编码为
[2^1, 3^2, 2^1, 3^2]
或者,
[2, 3, 2, 3] // primes
[1, 2, 1, 2] // exponents
现在,我们检查是否2^1 * 3^2 == 3^2 * 2^1
(第一个质数,第一个指数乘以最后一个质数,最后一个指数,然后与第二个质数相比较下一个)
既然成立,那么它是可减的。
让我们试试[b,b,b,b,b]
:
这可以编码为
[3^5]
或者,
[3] // primes
[5] // exponents
这是一个特殊情况:如果你有1个元素列表,那么你的原始列表是可缩小的。
让我们试试[b, b, b, b, a]
:
这可以编码为
[3^4, 2^1]
或者,
[3, 2] // primes
[4, 1] // exponents
我们检查是否 3^4 == 2^1
,由于不是这样,所以您的列表不可简化。
让我们尝试 [a, b, a, b, a, b]
:
这可以编码为
[2^1, 3^1, 2^1, 3^1, 2^1, 3^1]
或者,
[2, 3, 2, 3, 2, 3]
[1, 1, 1, 1, 1, 1]
尝试上述过程是有效的,因为 2^1 * 3^1 == 3^1 * 2^1 == 2^1 * 3^1
因此,算法应该像这样:
将所有数字编码为质数。
遍历列表,按以下方式创建两个列表并填充它们
现在您拥有两个列表p
和e
,它们的长度均为n
,请执行以下操作:
var start = p[0]^e[0] * p[n-1]^e[n-1]
var reducible = true;
for (int i = 0; i < n/2, ++i) :
if ( (p[i]^e[i] * p[n-i]^e[n-i]) != start ) :
reducible = false;
break;
注意:我并没有真正编写这个算法并尝试各种输入。这只是一个想法。
另外,如果一个列表是可约的,从它的长度和
n
的长度来看,将原始列表缩减到其基本形式应该不太困难。
第二个注意事项:如果有人发现上面有错误,请纠正我。由于时间已经很晚了,我的注意力可能不够集中,所以这些都可能行不通。
[a,b,b,c]
和[b,b,b,b,a]
的不可约性有什么规则?这个规则的直觉是什么?我问这个问题是因为它看起来像一个更一般的算法的特殊情况。根据你的第三条规则,[b,b]
将(递归地)简化为[b]
,[b,b,b,b] -> [b]
也将如此简化。 - I GIVE CRAP ANSWERS