魔方置乱算法- JavaScript

Question

我一直在一个魔方计时器网站上工作，我需要做一个加扰算法。我将研究一下置乱算法的工作原理:每一张脸都有自己的字母，它是初始的。例如，如果你想移动正面，你会写“F”。如果你想移动右边的脸，你会写“R”，等等。请注意，底面是D，至于向下。所以你有D，U，L，B，如果在那个字母之后没有什么，你顺时针转动它。如果有一个后缀“‘”，你就逆时针转动它。如果有一个2，你把它转两次。现在的问题是，你不能有两个相同的字母相邻一个，因为他们会取消(例如“..。你.“就等于什么都不做。到目前为止，我已经在算法中解决了这个问题。问题是，当你有一个字母，然后它是相反的，然后再次第一个字母，(例如“..。你.“(指顺时针向上，顺时针向上，逆时针向上)。我不知道如何检查这些，并避免它们自动。下面是代码：

<div id=“Scramble”></div>
<script>
generateScramble();

function generateScramble() {

  // Possible Letters
  var array = new Array(" U", " D", " R", " L", " F", " B")

  // Possible switches
  var switches = ["", "\'", "2"]; 

  var array2 = new Array(); // The Scramble.

  var last = ''; // Last used letter

  var random = 0;

  for (var i = 0; i < 20; i++) {
      // the following loop runs until the last one 
      // letter is another of the new one
      do {
         random = Math.floor(Math.random() * array.length);
      } while (last == array[random]) 

  // assigns the new one as the last one
  last = array[random];

  // the scramble item is the letter
  // with (or without) a switch
  var scrambleItem = array[random] + switches[parseInt(Math.random()*switches.length)];

  array2.push(scrambleItem); // Get letters in random order in the array.
  }

  var scramble = "Scramble: ";

  // Appends all scramble items to scramble variable
  for(i=0; i<20; i++) {
     scramble += array2[i];
  }

  document.getElementById("Scramble").innerHTML = scramble; // Display the scramble
}
</script>

Answer 1

对于初学者来说，上帝的号码是20代表魔方，所以你只能移动20次而不是25次。我假设您不是在做扰码(如标题所示)，而是为genere&测试解决程序类型生成解决方案命令字符串。有太多的序列相互取消，检查所有的序列很可能比实际的尝试要慢。

问题是，即使是O(n^20)也是巨大的，您需要降低20。这是通过LUT保持半解状态来完成的。例如，为所有5转置乱组合创建表保持状态。然后用它作为结束条件，把你的解算器变成O(n^15 + n^5) = O(n^15) .