有趣的排序问题

如果你使用宽度优先的蛮力,它仍然是蛮力,但至少你有保证想出最短的移动顺序,如果有答案的话。下面是一个使用宽度优先搜索的快速python解决方案。

from time import time

def generate(c):
    sep = "UU"
    c1, c2 = c.split(sep)
    for a in range(len(c1)-1):
        yield c1[0:a]+sep+c1[(a+2):]+c1[a:(a+2)]+c2
    for a in range(len(c2)-1):
        yield c1+c2[a:(a+2)]+c2[0:a]+sep+c2[(a+2):]

def solve(moves,used):
    solved = [cl for cl in moves if cl[-1].rindex('0') < cl[-1].index('1')]
    if len(solved) > 0: return solved[0]
    return solve([cl+[d] for cl in moves for d in generate(cl[-1]) if d not in used and not used.add(d)],used)

code = raw_input('enter the code:')

a = time()
print solve([[code]],set())
print "elapsed time:",(time()-a),"seconds"

我认为这应该有效:

• 重复一次以查找 如果他们不占领最后一个美国 两个点,移过去 swapping with the last two.
• 创建一个 用于跟踪当前 已排序的元素,最初设置为 array.length-1,表示任何内容 排序之后。
• 迭代 向后的。每次你遇到一个 1:
  • 将前面的一个及其元素与美国交换。
  • 将U替换回当前排序的元素跟踪器-1,更新变量
• 继续,直到数组开始。

这是一个很有趣的问题,所以我们试着解决它。我将从对问题的精确分析开始,看看能发现什么。在接下来的几天里,我会一个一个地把这个答案加起来。欢迎任何帮助。

尺寸问题 n 是一个问题 n 零点, n 两个,两个 U S,因此它由 2n+2 符号。

有

(2n)!
-----
(n!)²

完全不同的序列 n 零点和 n 那些。然后有 2n+1 插入两者的可能位置 U S,因此

(2n)!         (2n+1)!
-----(2n+1) = -------
(n!)²          (n!)²

大小的问题实例 n .

接下来,我将寻找一种方法来为每个问题实例分配一个分数,以及在所有可能的移动下该分数是如何变化的,希望找出所需移动的最小数量是多少。

大小为1的实例已排序

--01   0--1   01--

(我想我会用连字符代替 U 因为它们更容易识别)或者无法排序。

--10  ==only valid move==>  10--
-10-  no valid move
10--  ==only valid move==>  --10

因此我假设 n >= 2 .

我在考虑逆问题——从有序序列开始,可以得到什么无序序列。顺序序列是由两个连字符的位置决定的,所以下一个问题是是否可以从其他顺序到达每个顺序序列。因为一个移动序列可以向前和向后执行,所以足以表明一个特定的有序序列可以从所有其他序列中到达。我选择 (0|n)(1|n)-- . ( (0|x) 精确表示 x 零点。如果 X 不符合形式 n-m 假设为零或更多。可能会有其他约束,如 a+b+2=n 未明确说明。 ^^ 指示交换位置。0/1边界显然在最后一个零和第一个零之间。)

// n >= 2, at least two zeros between -- and the 0/1 border
(0|a)--(0|b)00(1|n) => (0|n)--(1|n-2)11 => (0|n)(1|n)--
            ^^                       ^^
// n >= 3, one zero between -- and 0/1 boarder
(0|n-1)--01(1|n-1) => (0|n)1--(1|n-3)11 => (0|n)(1|n)--
         ^^                          ^^
// n >= 2, -- after last zero but at least two ones after --          
(0|n)(1|a)--(1|b)11 => (0|n)(1|n)--
                 ^^
// n >= 3, exactly one one after --
(0|n)(1|n-3)11--1 => (0|n)(1|n-3)--111 => (0|n)(1|n)--
            ^^                      ^^
// n >= 0, nothing to move
(0|n)(1|n)--

对于剩下的两个问题的大小2- 0--011 和 001--1 -似乎不可能到达 0011-- . 所以 n >= 3 在最多四个动作中(可能在所有情况下都更少,因为我认为最好是选择 (0|n)--(1|n) 但我把这个留到明天。初步目标是找出一个人能以什么样的速度和在什么样的条件下创造(并由此消除) 010 和 101 因为它们似乎是其他人已经提到过的最困难的情况。

首先让我想到的是自顶向下的动态编程方法。这有点容易理解,但会消耗很多记忆。当我尝试应用自下而上的方法时,您可以尝试以下方法:

想法很简单-缓存所有的搜索结果以进行暴力搜索。它会变成这样:

function findBestStep(currentArray, cache) {
    if (!cache.contains(currentArray)) {
        for (all possible moves) {
            find best move recursively
        }
        cache.set(currentArray, bestMove);
    } 

    return cache.get(currentArray);
}

这种方法的复杂性是…o(2^n),令人毛骨悚然。然而,我看不出任何合乎逻辑的方法,它可以更小,因为任何移动都是允许的。

如果找到一种应用自下而上算法的方法,它可能会更快(不需要缓存),但它仍然具有O(2^n)复杂性。

补充: 好的,我用Java实现了这个东西。代码很长,因为它总是在Java中,所以不要害怕它的大小。主算法非常简单,可以在底部找到。我认为没有比这更快的方法了(如果可以更快的话,这更像是一个数学问题)。它消耗了几吨的内存,但仍然计算得很快。 这个 0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2 在1秒内计算,占用~60MB内存,导致7步排序。

public class Main {

    public static final int UU_CODE = 2;

    public static void main(String[] args) {
        new Main();
    }

    private static class NumberSet {
        private final int uuPosition;
        private final int[] numberSet;
        private final NumberSet parent;

        public NumberSet(int[] numberSet) {
            this(numberSet, null, findUUPosition(numberSet));
        }

        public NumberSet(int[] numberSet, NumberSet parent, int uuPosition) {
            this.numberSet = numberSet;
            this.parent = parent;
            this.uuPosition = uuPosition;
        }

        public static int findUUPosition(int[] numberSet) {
            for (int i=0;i<numberSet.length;i++) {
                if (numberSet[i] == UU_CODE) {
                    return i;
                }
            }
            return -1;
        }

        protected NumberSet getNextNumberSet(int uuMovePos) {
            final int[] nextNumberSet = new int[numberSet.length];
            System.arraycopy(numberSet, 0, nextNumberSet, 0, numberSet.length);
            System.arraycopy(this.getNumberSet(), uuMovePos, nextNumberSet, uuPosition, 2);
            System.arraycopy(this.getNumberSet(), uuPosition, nextNumberSet, uuMovePos, 2);
            return new NumberSet(nextNumberSet, this, uuMovePos);
        }

        public Collection<NumberSet> getNextPositionalSteps() {
            final Collection<NumberSet> result = new LinkedList<NumberSet>();

            for (int i=0;i<=numberSet.length;i++) {
                final int[] nextNumberSet = new int[numberSet.length+2];
                System.arraycopy(numberSet, 0, nextNumberSet, 0, i);
                Arrays.fill(nextNumberSet, i, i+2, UU_CODE);
                System.arraycopy(numberSet, i, nextNumberSet, i+2, numberSet.length-i);
                result.add(new NumberSet(nextNumberSet, this, i));
            }
            return result;
        }

        public Collection<NumberSet> getNextSteps() {
            final Collection<NumberSet> result = new LinkedList<NumberSet>();

            for (int i=0;i<=uuPosition-2;i++) {
                result.add(getNextNumberSet(i));
            }

            for (int i=uuPosition+2;i<numberSet.length-1;i++) {
                result.add(getNextNumberSet(i));
            }

            return result;
        }

        public boolean isFinished() {
            boolean ones = false;
            for (int i=0;i<numberSet.length;i++) {
                if (numberSet[i] == 1)
                    ones = true;
                else if (numberSet[i] == 0 && ones)
                    return false;
            }
            return true;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final NumberSet other = (NumberSet) obj;
            if (!Arrays.equals(this.numberSet, other.numberSet)) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Arrays.hashCode(this.numberSet);
            return hash;
        }

        public int[] getNumberSet() {
            return this.numberSet;
        }

        public NumberSet getParent() {
            return parent;
        }

        public int getUUPosition() {
            return uuPosition;
        }
    }

    void precacheNumberMap(Map<NumberSet, NumberSet> setMap, int length, NumberSet endSet) {
        int[] startArray = new int[length*2];
        for (int i=0;i<length;i++) startArray[i]=0;
        for (int i=length;i<length*2;i++) startArray[i]=1;
        NumberSet currentSet = new NumberSet(startArray);

        Collection<NumberSet> nextSteps = currentSet.getNextPositionalSteps();
        List<NumberSet> nextNextSteps = new LinkedList<NumberSet>();
        int depth = 1;

        while (nextSteps.size() > 0) {
            for (NumberSet nextSet : nextSteps) {
                if (!setMap.containsKey(nextSet)) {
                    setMap.put(nextSet, nextSet);
                    nextNextSteps.addAll(nextSet.getNextSteps());
                    if (nextSet.equals(endSet)) {
                        return;
                    }
                }
            }
            nextSteps = nextNextSteps;
            nextNextSteps = new LinkedList<NumberSet>();
            depth++;
        }
    }

    public Main() {
        final Map<NumberSet, NumberSet> cache = new HashMap<NumberSet, NumberSet>();
        final NumberSet startSet = new NumberSet(new int[] {0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2});

        precacheNumberMap(cache, (startSet.getNumberSet().length-2)/2, startSet);

        if (cache.containsKey(startSet) == false) {
            System.out.println("No solutions");
        } else {
            NumberSet cachedSet = cache.get(startSet).getParent();
            while (cachedSet != null && cachedSet.parent != null) {
                System.out.println(cachedSet.getUUPosition());
                cachedSet = cachedSet.getParent();
            }
        }
    }
}

这里有一个尝试:

Start:
  let c1 = the total number of 1s
  let c0 = the total number of 0s
  if the UU is at the right end of the string, goto StartFromLeft
StartFromRight
  starting at the right end of the string, move left, counting 1s, 
  until you reach a 0 or the UU.  
  If you've reached the UU, goto StartFromLeft.
  If the count of 1s equals c1, you are done.  
  Else, swap UU with the 0 and its left neighbor if possible.  
  If not, goto StartFromLeft.
StartFromLeft
  starting at the left end of the string, move right, counting 0s,
  until you reach a 1 or the UU.
  If you've reached the UU, goto StartFromRight.
  If the count of 0s equals c0, you are done.
  Else, swap UU with the 1 and its right neighbor, if possible.  
  If not, goto StartFromRight
  Then goto StartFromRight.

因此,对于原始1100UUU0011:

1100UU0011 - original
110000UU11 - start from right, swap UU with 00
UU00001111 - start from left, swap UU with 11

对于狡猾的0101U01

0101UU01 - original
0UU11001 - start from right, can't swap UU with U0, so start from left and swap UU with 10
00011UU1 - start from right, swap UU with 00

然而,这并不能解决01uuu0之类的问题……但是可以通过一个标志来解决这个问题——如果你已经完成了整个算法,没有进行任何交换,并且没有解决……做点什么。

关于这个问题…它从不要求最优的解决方案,而这些类型的问题不希望这样。您需要编写一个通用的算法来处理这个问题,而对于长度可能为兆字节的字符串,使用蛮力搜索来找到最佳解决方案是不可行的。我也很晚才注意到,0和1的数目肯定是一样的,但我认为在一般情况下,0和1的数目可能不同,这更有趣。实际上,如果输入字符串的长度小于7,就不能保证在每种情况下都有解决方案,即使在20和1的情况下Nd 2 1s。

3号:只有一个数字,所以按定义排序(UUU0 UU1 0UU 1UU)

4号:没有办法改变顺序。如果UU位于中间,则没有移动,只有当UU位于末尾时才与两位数字交换(1UU0不移动,UU10->10UU->UUU10等)

Size 5: UU in the middle can only move to the far end and not change the order of the 0s and 1s (1UU10->110UU). 一端的UU可以移动到中间,而不是更改订单,但只能移回同一端,这样它就没有任何用处(UU110->11UU0->UUU110)。唯一改变数字的方法是如果UU在一端,并与另一端交换。(UUABC->BCAUU或ABCUU->UUCAB)。这意味着,如果UU位于0或2,它可以解决0是否在中间(UU101->011UU或UU100->001UU),如果UU位于1或3,它可以解决1是否在中间(010UU->UUU001或110UU->UUU011)。其他问题已经解决或无法解决。如果我们需要处理这个案例,我会说硬编码。如果排序,则返回结果(无移动)。如果UU在中间的某个地方,把它移到末尾。从一端交换到另一端,这是唯一可能的交换,无论现在是否排序。

尺寸6:现在我们得到了这样一个位置,我们可以根据规则指定一个字符串,在那里我们可以移动,但没有解决方案。这是任何算法的问题点,因为我认为任何解决方案的一个条件都应该是它会让您知道它是否无法解决。例如,0010、0100、1000、1011、1100、1101和1110可以解决,无论UU在哪里,最坏的情况需要4个步骤来解决。只有当UU处于奇数位置时,才能求解0101和1010。0110和1001只能在UU处于偶数位置(两端或中间)时求解。

我认为最好的方法是像下面这样,但我还没有写出来。首先,确保将“1”放在列表的末尾。如果结尾当前为0,请将UU移动到结尾,然后将其移动到最后一个“1”位置-1。在这之后,您继续将UU移动到第一个“1”,然后移动到新UU之后的第一个“0”。这会将所有0移动到列表的开头。另一方面,我也看到过类似的答案,但没有考虑到最后一个角色。这可能会遇到小值的问题(即,001UUU01,不能移动到第一个1,移动到结尾00101UU,允许我们移动到开头,但在结尾00UUU110处保留0)。

我猜你可以硬编码这样的特殊情况。不过,我想可能有更好的算法。例如,您可以使用前两个字符作为“临时交换变量”。您将把UU放在那里,然后对其他人进行组合操作,以便在开始时离开UY。例如,uuuabcde可以用cd交换ab,或者用de交换de或bc(bcauude->bcadeuu->uuadebc)。

另一种可能的方法是将字符视为两个由两个基3位组成的块。 0101U0101将显示为11C11或3593。也可能是硬编码交换的组合。例如,如果您看到11UU,请将UU向左移动2。如果你看到UU00,把UU右移两个。如果看到UU100或UU101,请向右移动UU 2以获得001UU或011UU。

也许另一种可能是一些算法将0向左移动到中心,1向右移动到中心(如果给定0和1的数目相同的话)。

也许在一个只包含0和1的结构上工作会更好,这个结构有一个UU的位置。

也许更好地观察结果条件,允许UU在字符串中的任何位置,必须满足这些条件: 长度后没有0/2 前1号(长度/2-1)

也许还有更一般的规则,比如在这种情况下用10交换UU真的很好,因为“0”在UU之后,这会让您将新的00移回10的位置(10111UU->UUU111100->001111UU)。

总之,这是C中的蛮力代码。输入是一个字符串和一个空字典。它用每个可能的结果字符串作为键填充字典,并以最短步骤列表作为值:

呼叫:

m_Steps = new Dictionary<string, List<string>>();
DoSort("UU1010011101", new List<string>);

它包括dotests(),它为具有给定位数(不包括uu)的每个可能字符串调用dosort:

Dictionary<string, List<string>> m_Steps = new Dictionary<string, List<string>>();

public void DoStep(string state, List<string> moves) {
 if (m_Steps.ContainsKey(state) && m_Steps[state].Count <= moves.Count + 1) // have better already
  return;

 // we have a better (or new) solution to get to this state, so set it to the moves we used to get here
 List<string> newMoves = new List<string>(moves);
 newMoves.Add(state);
 m_Steps[state] = newMoves;

 // if the state is a valid solution, stop here
 if (state.IndexOf('1') > state.LastIndexOf('0'))
  return;

 // try all moves
 int upos = state.IndexOf('U');
 for (int i = 0; i < state.Length - 1; i++) {
  // need to be at least 2 before or 2 after the UU position (00UU11 upos is 2, so can only move to 0 or 4)
  if (i > upos - 2 && i < upos + 2)
   continue;

  char[] chars = state.ToCharArray();
  chars[upos] = chars[i];
  chars[upos + 1] = chars[i + 1];
  chars[i] = chars[i + 1] = 'U';
  DoStep(new String(chars), newMoves);
 }
}

public void DoTests(int digits) { // try all combinations
 char[] chars = new char[digits + 2];
 for (int value = 0; value < (2 << digits); value++) {
  for (int uupos = 0; uupos < chars.Length - 1; uupos++) {
   for (int i = 0; i < chars.Length; i++) {
    if (i < uupos)
     chars[i] = ((value >> i) & 0x01) > 0 ? '1' : '0';
    else if (i > uupos + 1)
     chars[i] = ((value >> (i - 2)) & 0x01) > 0 ? '1' : '0';
    else
     chars[i] = 'U';
   }
   m_Steps = new Dictionary<string, List<string>>();
   DoSort(new string(chars), new List<string>);
   foreach (string key in m_Steps.AllKeys))
    if (key.IndexOf('1') > key.LastIndexOf('0')) { // winner
     foreach (string step in m_Steps[key])
      Console.Write("{0}\t", step);
     Console.WriteLine();
    }
  }
 }
}

Counting sort .

如果a是0的个数,a也是1的个数,u是我们的个数:

for(int i=0; i<A; i++)
   data[i] = '0';
for(int i=0; i<A; i++)
   data[A+i] = '1';
for(int i=0; i<U; i++)
   data[A+A+i] = 'U';

只有两个我们?

为什么不计算0的个数并存储美国的位置呢?

numberOfZeros = 0
uPosition = []
for i, value in enumerate(sample):
    if value = 0:
        numberOfZeros += 1
    if value = U
       uPosition.append(i)

result = []
for i in range(len(sample)):
    if i = uPosition[0]
       result.append('U')
       uPosition.pop(0)
       continue
    if numberOfZeros > 0:
       result.append('0')
       numberOfZeros -= 1
       continue
    result.append('1')

会导致运行时为O(n)

甚至更好:

result = []
numberOfZeros = (len(sample)-2)/2
for i, value in enumerate(sample):
    if value = U
       result.append('U')
       continue
    if numberOfZeros > 0:
       result.append(0)
       numberOfZeros -= 1
       continue
    result.append(1)