I tried to solve a programming problem but my I was unable to see an efficient algorithm. Situation is like this: We have a set of n lamps which can be on (1) or off (0) like this: 1110001011101. That byte string means that there are 13 lamps forming a circle where first three lamps are on, then 3 next off and so on and circle mean that the last lamp is next to the first one.
我试图解决一个编程问题,但我无法看到一个有效的算法。情况是这样的:我们有一组n个灯可以开启(1)或关闭(0),如下所示:1110001011101。该字节串意味着有13个灯形成一个圆形,前三个灯亮,然后3个下一个关闭,依此类推,圆圈表示最后一盏灯与第一盏灯相邻。
Then we have been given an integer m>0. It means that in any turn we can choose a lamp and then it and its m adjacent lamps changes their state s to 1-s. I.e. if m=2 and lamp states are 1110001011101 then applying the process to the first lamp we get the sequence 0000001011110.
然后我们给出了一个整数m> 0。这意味着在任何一个转弯中我们都可以选择一个灯,然后它和它的m个相邻的灯将它们的状态改变为1-s。即如果m = 2且灯状态为1110001011101,则将该过程应用于第一个灯,我们得到序列0000001011110。
Now the question is that if the string of length about 2200 and m about 110 are fixed, how one can develop an algorithm that shut downs all the lamps with minimum number of turns?
现在的问题是,如果长度大约为2200和大约110的字符串是固定的,那么如何开发一种能够以最小匝数关闭所有灯的算法?
3 个解决方案
#1
There's a general solution to flipping problems like this using linear algebra over Z/2Z (that is the field containing only the numbers 0 and 1).
使用Z / 2Z上的线性代数(即仅包含数字0和1的字段)可以解决这样的问题。
Suppose there's N bulbs and N switches. Let M be an N by N matrix with a 1 in position i, j if pressing switch i toggles bulb j. Here your matrix will look like this for N=5, m=1:
假设有N个灯泡和N个开关。令M为N×N矩阵,如果按下开关i切换灯泡j,则位置i,j为1。对于N = 5,m = 1,你的矩阵看起来像这样:
1, 1, 0, 0, 1
1, 1, 1, 0, 0
0, 1, 1, 1, 0
0, 0, 1, 1, 1
1, 0, 0, 1, 1
Let x be a column vector of size N, where each entry is 0 or 1.
令x为大小为N的列向量,其中每个条目为0或1。
Then Mx (that is, the product of the matrix M and the vector x over Z/2Z) is a column vector of size N which is the result of pressing the switches corresponding to 1s in x. That's because in Z/2Z, multiplication is like "and" and addition is like "xor".
然后Mx(即,矩阵M和矢量x在Z / 2Z上的乘积)是大小为N的列向量,其是对应于x中的1s的开关的结果。那是因为在Z / 2Z中,乘法就像“和”,加法就像“xor”。
Let v be a column vector of size N, with v_i=1 if bulb i is initially lit. Then x solves the problem if it's a solution to the linear system Mx = v. It can be solved, for example, using gaussian elimination.
令v为大小为N的列向量,如果灯泡i最初被点亮,则v_i = 1。然后x解决了问题,如果它是线性系统的解Mx = v。它可以解决,例如,使用高斯消元法。
#2
This problem is similar to the well-known "lights out" problem. http://en.wikipedia.org/wiki/Lights_Out_%28game%29 One way to approach it is by using linear algebra. It's easier to understand with smaller numbers, say length = 5 and m = 1.
这个问题类似于众所周知的“熄灯”问题。 http://en.wikipedia.org/wiki/Lights_Out_%28game%29接近它的一种方法是使用线性代数。使用较小的数字更容易理解,比如长度= 5和m = 1。
First note that choosing a lamp and changing it (and its neighbors') state twice has no effect. Second note that the order in which lamps (and their neighbors) are switch doesn't matter. So a strategy is just a set of lamps. We'll represent lamps that are chosen to be part of the strategy by 1 and lamps that are not chosen by 0. We place the 1's and 0's in a column vector, e.g., (0 1 1 0 1)^T where T is for transpose (rows become columns). That strategy means toggle the lamp in position 1 (starting at position 0, of course) and its two neighbors; then the lamp in position 2 and its two neighbors, and finally the lamp in position 4 and its two neighbors.
首先请注意,选择一盏灯并将其更改(及其邻居)状态两次都没有效果。第二个注意事项,灯(及其邻居)的切换顺序无关紧要。所以策略只是一组灯。我们将代表被选择作为策略一部分的灯和未被0选择的灯。我们将1和0放在列向量中,例如,(0 1 1 0 1)^ T其中T是用于转置(行成为列)。该策略意味着将灯泡切换到位置1(当然从位置0开始)及其两个邻居;然后灯在位置2和它的两个邻居,最后灯位于位置4和它的两个邻居。
The effect of a strategy can be calculated by matrix multiplication over the field GF(2). GF(2) has just 2 elements, 0 and 1, with ordinary rules of arithmetic except for the rule 1 + 1 = 0. Then the effect of the strategy above is the result of matrix multiplication by a matrix with the result of choosing lamp i in the i-th column, in other words by a "circulant matrix` as follows:
可以通过字段GF(2)上的矩阵乘法来计算策略的效果。 GF(2)只有2个元素,0和1,除了规则1 + 1 = 0之外还有普通的算术规则。然后上面策略的效果是矩阵乘以矩阵的结果,选择灯的结果我在第i列,换句话说,通过“循环矩阵”如下:
[ 1 1 0 0 1 ] [0] [0]
[ 1 1 1 0 0 ] [1] [0]
[ 0 1 1 1 0 ] [1] = [0]
[ 0 0 1 1 1 ] [0] [0]
[ 1 0 0 1 1 ] [1] [1]
The result of the strategy (0 1 1 0 1)^T is to toggle only the light in the last position. So if you start with only the light in the last position lit, and apply the strategy, all the lights will be off.
策略(0 1 1 0 1)^ T的结果是仅切换最后位置的灯。因此,如果您只开始点亮最后一个位置的灯光并应用策略,则所有灯光都将熄灭。
In this simple case, we represent the initial configuration by a column vector b. The solution strategy is then a column vector x satisfying the matrix equation Ax = b.
在这个简单的例子中,我们用列向量b表示初始配置。然后,求解策略是满足矩阵方程Ax = b的列向量x。
The question now becomes, for given b, 1) is there an x satisfying Ax=b? 2) Is the solution x unique? If not, which x has the least 1's? 3) How can it be calculated?
现在的问题是,对于给定的b,1)是否存在满足Ax = b的x? 2)解决方案x是否独一无二?如果没有,哪个x至少有1个? 3)如何计算?
The answers to the above questions will depend on the numbers "length" and "m" for the particular problem at hand. In the length = 5, m = 1 problem considered above, the theory of linear algebra tells us that there is a unique solution for any b. We can get solutions for b of the form (0 0 ... 1 ... 0)^T, in other words one 1 and the rest zero, by "rotating" the solution (0 1 1 0 1)^T. We can represent any solution uniquely as a linear combination of those solutions, so the strategy/solution with the minimum number of 1's is the same as the unique solution for any given initial state.
上述问题的答案将取决于手头特定问题的数字“长度”和“m”。在上面考虑的长度= 5,m = 1的问题中,线性代数理论告诉我们任何b都有一个唯一的解。通过“旋转”解(0 1 1 0 1)^ T,我们可以得到形式为(0 0 ... 1 ... 0)^ T的b的解,换句话说,1为1,其余为零。我们可以将任何解决方案唯一地表示为这些解决方案的线性组合,因此具有最小数量1的策略/解决方案与任何给定初始状态的唯一解决方案相同。
On the other hand, with length = 6 and m = 1, all three strategies (100100)^T, (010010)^T, and (001001)^T map to outcome (111111)^T, so that there is not a unique solution in some cases; by the theory of linear algebra, it follows that there is no solution in some other cases.
另一方面,当长度= 6且m = 1时,所有三个策略(100100)^ T,(010010)^ T和(001001)^ T映射到结果(111111)^ T,因此没有某些情况下的独特解决方案根据线性代数理论,在其他一些情况下没有解决方案。
In general, we can tell whether solutions exist and are unique using Gaussian elimination. In the 5x5 case above, add row 0 to rows 1 and 4;
一般来说,我们可以使用高斯消元来判断解是否存在并且是唯一的。在上面的5x5情况下,将行0添加到第1行和第4行;
[ 1 1 0 0 1 ] [1 0 0 0 0] [ 1 1 0 0 1 ] [1 0 0 0 0]
[ 1 1 1 0 0 ] [0 1 0 0 0] [ 0 0 1 0 1 ] [1 1 0 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] -> [ 0 1 1 1 0 ] [0 0 1 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0] [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 1 0 0 1 1 ] [0 0 0 0 1] [ 0 1 0 1 0 ] [1 0 0 0 1]
then swap rows 1 and 2; then add row 1 to row 0 and row 4,
然后交换第1行和第2行;然后将第1行添加到第0行和第4行,
[ 1 1 0 0 1 ] [1 0 0 0 0] [ 1 0 1 1 1 ] [1 0 1 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] [ 0 1 1 1 0 ] [0 0 1 0 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0] [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 0 1 0 1 0 ] [1 0 0 0 1] [ 0 0 1 0 0 ] [1 0 1 0 1]
then add row 2 to rows 0, 1, 3, 4; then add row 3 to rows 1, 2;
然后将第2行添加到第0,1,3,4行;然后将第3行添加到第1,2行;
[ 1 0 0 1 0 ] [0 1 1 0 0] [ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 1 1 ] [1 1 1 0 0] [ 0 1 0 0 1 ] [0 0 1 1 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 0 1 0 ] [1 1 0 1 0] [ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1] [ 0 0 0 0 1 ] [0 1 1 0 1]
and finally add row 4 to rows 1, 2:
最后将第4行添加到第1,2行:
[ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 0 0 ] [0 1 0 1 1]
[ 0 0 1 0 0 ] [1 0 1 0 1]
[ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]
You can read off the basis of solutions in the columns of the right matrix. For example, the solution we used above is in the last column of the right matrix.
您可以在正确矩阵的列中读取解决方案的基础。例如,我们上面使用的解决方案位于右矩阵的最后一列。
You should try Gaussian elimination in the length = 6, m = 1 case discussed above to see what happens.
您应该尝试在上面讨论的长度= 6,m = 1的情况下进行高斯消除,看看会发生什么。
In the given case (length = 2200, m = 110), I suspect that solutions always exist and are unique because the number of lamps toggled in one move is 221, which is relatively prime to 2200, but I suggest you use Gaussian elimination to find an explicit strategy for any starting position b. How would you minimize the number of moves if there were not a unique strategy?
在给定的情况下(长度= 2200,m = 110),我怀疑解决方案总是存在并且是唯一的,因为在一次移动中切换的灯的数量是221,这相对于2200是相对的,但我建议你使用高斯消除找到任何起始位置的明确策略b。如果没有独特的策略,您会如何最大限度地减少移动次数?
#3
Well, your explanation doesn't make it clear if the lamps should be only turned off or "flipped" (i.e., 0's become 1's and 1's become 0's). Your example data just turns them off.
那么,你的解释并没有说明灯是否应该只关闭或“翻转”(即0变为1,1变为0)。您的示例数据只会将其关闭。
If that's the case, just set the 110 lamps to 0 - that would be quicker than querying their state before switching them off. Assuming your lamps are in an array called "lamps" and the starting lamp position is startPos:
如果是这种情况,只需将110灯设置为0 - 这比在关闭之前查询状态要快。假设您的灯位于一个名为“灯”的阵列中,起始灯位置为startPos:
// These first 2 lines added after Kolmar remark about adjacent lamps meaning lamps to the left and right.
startPos = startPos - m;
if (startPos < 0) startPos += lamps.length;
for (int i=0; i <= m + 1; i++){
if ((i + startPos) > lamps.length) startPos = 0;
lamps[i + startPos] = 0;
}
If you need to "flip" the lamp's state, change the last line of the loop to:
如果您需要“翻转”灯泡的状态,请将循环的最后一行更改为:
lamps[i + startPos] = 1-lamps[i + startPos];
#1
There's a general solution to flipping problems like this using linear algebra over Z/2Z (that is the field containing only the numbers 0 and 1).
使用Z / 2Z上的线性代数(即仅包含数字0和1的字段)可以解决这样的问题。
Suppose there's N bulbs and N switches. Let M be an N by N matrix with a 1 in position i, j if pressing switch i toggles bulb j. Here your matrix will look like this for N=5, m=1:
假设有N个灯泡和N个开关。令M为N×N矩阵,如果按下开关i切换灯泡j,则位置i,j为1。对于N = 5,m = 1,你的矩阵看起来像这样:
1, 1, 0, 0, 1
1, 1, 1, 0, 0
0, 1, 1, 1, 0
0, 0, 1, 1, 1
1, 0, 0, 1, 1
Let x be a column vector of size N, where each entry is 0 or 1.
令x为大小为N的列向量,其中每个条目为0或1。
Then Mx (that is, the product of the matrix M and the vector x over Z/2Z) is a column vector of size N which is the result of pressing the switches corresponding to 1s in x. That's because in Z/2Z, multiplication is like "and" and addition is like "xor".
然后Mx(即,矩阵M和矢量x在Z / 2Z上的乘积)是大小为N的列向量,其是对应于x中的1s的开关的结果。那是因为在Z / 2Z中,乘法就像“和”,加法就像“xor”。
Let v be a column vector of size N, with v_i=1 if bulb i is initially lit. Then x solves the problem if it's a solution to the linear system Mx = v. It can be solved, for example, using gaussian elimination.
令v为大小为N的列向量,如果灯泡i最初被点亮,则v_i = 1。然后x解决了问题,如果它是线性系统的解Mx = v。它可以解决,例如,使用高斯消元法。
#2
This problem is similar to the well-known "lights out" problem. http://en.wikipedia.org/wiki/Lights_Out_%28game%29 One way to approach it is by using linear algebra. It's easier to understand with smaller numbers, say length = 5 and m = 1.
这个问题类似于众所周知的“熄灯”问题。 http://en.wikipedia.org/wiki/Lights_Out_%28game%29接近它的一种方法是使用线性代数。使用较小的数字更容易理解,比如长度= 5和m = 1。
First note that choosing a lamp and changing it (and its neighbors') state twice has no effect. Second note that the order in which lamps (and their neighbors) are switch doesn't matter. So a strategy is just a set of lamps. We'll represent lamps that are chosen to be part of the strategy by 1 and lamps that are not chosen by 0. We place the 1's and 0's in a column vector, e.g., (0 1 1 0 1)^T where T is for transpose (rows become columns). That strategy means toggle the lamp in position 1 (starting at position 0, of course) and its two neighbors; then the lamp in position 2 and its two neighbors, and finally the lamp in position 4 and its two neighbors.
首先请注意,选择一盏灯并将其更改(及其邻居)状态两次都没有效果。第二个注意事项,灯(及其邻居)的切换顺序无关紧要。所以策略只是一组灯。我们将代表被选择作为策略一部分的灯和未被0选择的灯。我们将1和0放在列向量中,例如,(0 1 1 0 1)^ T其中T是用于转置(行成为列)。该策略意味着将灯泡切换到位置1(当然从位置0开始)及其两个邻居;然后灯在位置2和它的两个邻居,最后灯位于位置4和它的两个邻居。
The effect of a strategy can be calculated by matrix multiplication over the field GF(2). GF(2) has just 2 elements, 0 and 1, with ordinary rules of arithmetic except for the rule 1 + 1 = 0. Then the effect of the strategy above is the result of matrix multiplication by a matrix with the result of choosing lamp i in the i-th column, in other words by a "circulant matrix` as follows:
可以通过字段GF(2)上的矩阵乘法来计算策略的效果。 GF(2)只有2个元素,0和1,除了规则1 + 1 = 0之外还有普通的算术规则。然后上面策略的效果是矩阵乘以矩阵的结果,选择灯的结果我在第i列,换句话说,通过“循环矩阵”如下:
[ 1 1 0 0 1 ] [0] [0]
[ 1 1 1 0 0 ] [1] [0]
[ 0 1 1 1 0 ] [1] = [0]
[ 0 0 1 1 1 ] [0] [0]
[ 1 0 0 1 1 ] [1] [1]
The result of the strategy (0 1 1 0 1)^T is to toggle only the light in the last position. So if you start with only the light in the last position lit, and apply the strategy, all the lights will be off.
策略(0 1 1 0 1)^ T的结果是仅切换最后位置的灯。因此,如果您只开始点亮最后一个位置的灯光并应用策略,则所有灯光都将熄灭。
In this simple case, we represent the initial configuration by a column vector b. The solution strategy is then a column vector x satisfying the matrix equation Ax = b.
在这个简单的例子中,我们用列向量b表示初始配置。然后,求解策略是满足矩阵方程Ax = b的列向量x。
The question now becomes, for given b, 1) is there an x satisfying Ax=b? 2) Is the solution x unique? If not, which x has the least 1's? 3) How can it be calculated?
现在的问题是,对于给定的b,1)是否存在满足Ax = b的x? 2)解决方案x是否独一无二?如果没有,哪个x至少有1个? 3)如何计算?
The answers to the above questions will depend on the numbers "length" and "m" for the particular problem at hand. In the length = 5, m = 1 problem considered above, the theory of linear algebra tells us that there is a unique solution for any b. We can get solutions for b of the form (0 0 ... 1 ... 0)^T, in other words one 1 and the rest zero, by "rotating" the solution (0 1 1 0 1)^T. We can represent any solution uniquely as a linear combination of those solutions, so the strategy/solution with the minimum number of 1's is the same as the unique solution for any given initial state.
上述问题的答案将取决于手头特定问题的数字“长度”和“m”。在上面考虑的长度= 5,m = 1的问题中,线性代数理论告诉我们任何b都有一个唯一的解。通过“旋转”解(0 1 1 0 1)^ T,我们可以得到形式为(0 0 ... 1 ... 0)^ T的b的解,换句话说,1为1,其余为零。我们可以将任何解决方案唯一地表示为这些解决方案的线性组合,因此具有最小数量1的策略/解决方案与任何给定初始状态的唯一解决方案相同。
On the other hand, with length = 6 and m = 1, all three strategies (100100)^T, (010010)^T, and (001001)^T map to outcome (111111)^T, so that there is not a unique solution in some cases; by the theory of linear algebra, it follows that there is no solution in some other cases.
另一方面,当长度= 6且m = 1时,所有三个策略(100100)^ T,(010010)^ T和(001001)^ T映射到结果(111111)^ T,因此没有某些情况下的独特解决方案根据线性代数理论,在其他一些情况下没有解决方案。
In general, we can tell whether solutions exist and are unique using Gaussian elimination. In the 5x5 case above, add row 0 to rows 1 and 4;
一般来说,我们可以使用高斯消元来判断解是否存在并且是唯一的。在上面的5x5情况下,将行0添加到第1行和第4行;
[ 1 1 0 0 1 ] [1 0 0 0 0] [ 1 1 0 0 1 ] [1 0 0 0 0]
[ 1 1 1 0 0 ] [0 1 0 0 0] [ 0 0 1 0 1 ] [1 1 0 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] -> [ 0 1 1 1 0 ] [0 0 1 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0] [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 1 0 0 1 1 ] [0 0 0 0 1] [ 0 1 0 1 0 ] [1 0 0 0 1]
then swap rows 1 and 2; then add row 1 to row 0 and row 4,
然后交换第1行和第2行;然后将第1行添加到第0行和第4行,
[ 1 1 0 0 1 ] [1 0 0 0 0] [ 1 0 1 1 1 ] [1 0 1 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] [ 0 1 1 1 0 ] [0 0 1 0 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0] [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 0 1 0 1 0 ] [1 0 0 0 1] [ 0 0 1 0 0 ] [1 0 1 0 1]
then add row 2 to rows 0, 1, 3, 4; then add row 3 to rows 1, 2;
然后将第2行添加到第0,1,3,4行;然后将第3行添加到第1,2行;
[ 1 0 0 1 0 ] [0 1 1 0 0] [ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 1 1 ] [1 1 1 0 0] [ 0 1 0 0 1 ] [0 0 1 1 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 0 1 0 ] [1 1 0 1 0] [ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1] [ 0 0 0 0 1 ] [0 1 1 0 1]
and finally add row 4 to rows 1, 2:
最后将第4行添加到第1,2行:
[ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 0 0 ] [0 1 0 1 1]
[ 0 0 1 0 0 ] [1 0 1 0 1]
[ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]
You can read off the basis of solutions in the columns of the right matrix. For example, the solution we used above is in the last column of the right matrix.
您可以在正确矩阵的列中读取解决方案的基础。例如,我们上面使用的解决方案位于右矩阵的最后一列。
You should try Gaussian elimination in the length = 6, m = 1 case discussed above to see what happens.
您应该尝试在上面讨论的长度= 6,m = 1的情况下进行高斯消除,看看会发生什么。
In the given case (length = 2200, m = 110), I suspect that solutions always exist and are unique because the number of lamps toggled in one move is 221, which is relatively prime to 2200, but I suggest you use Gaussian elimination to find an explicit strategy for any starting position b. How would you minimize the number of moves if there were not a unique strategy?
在给定的情况下(长度= 2200,m = 110),我怀疑解决方案总是存在并且是唯一的,因为在一次移动中切换的灯的数量是221,这相对于2200是相对的,但我建议你使用高斯消除找到任何起始位置的明确策略b。如果没有独特的策略,您会如何最大限度地减少移动次数?
#3
Well, your explanation doesn't make it clear if the lamps should be only turned off or "flipped" (i.e., 0's become 1's and 1's become 0's). Your example data just turns them off.
那么,你的解释并没有说明灯是否应该只关闭或“翻转”(即0变为1,1变为0)。您的示例数据只会将其关闭。
If that's the case, just set the 110 lamps to 0 - that would be quicker than querying their state before switching them off. Assuming your lamps are in an array called "lamps" and the starting lamp position is startPos:
如果是这种情况,只需将110灯设置为0 - 这比在关闭之前查询状态要快。假设您的灯位于一个名为“灯”的阵列中,起始灯位置为startPos:
// These first 2 lines added after Kolmar remark about adjacent lamps meaning lamps to the left and right.
startPos = startPos - m;
if (startPos < 0) startPos += lamps.length;
for (int i=0; i <= m + 1; i++){
if ((i + startPos) > lamps.length) startPos = 0;
lamps[i + startPos] = 0;
}
If you need to "flip" the lamp's state, change the last line of the loop to:
如果您需要“翻转”灯泡的状态,请将循环的最后一行更改为:
lamps[i + startPos] = 1-lamps[i + startPos];