是否可以在o(n)中重新排列数组?

我认为应该这样做:

static <T> void arrange(T[] data, int[] p) {
    boolean[] done = new boolean[p.length];        
    for (int i = 0; i < p.length; i++) {
        if (!done[i]) {
            T t = data[i];
            for (int j = i;;) {
                done[j] = true;

                if (p[j] != i) {
                    data[j] = data[p[j]];
                    j = p[j];
                } else {
                    data[j] = t;
                    break;
                }
            }                
        }
    }
}

注意:这是Java。如果在没有垃圾收集的语言中执行此操作,请确保删除 done .

如果您关心空间,可以使用位集 完成 .我假设您可以为每个元素提供额外的位,因为您似乎愿意使用排列数组,它的大小是该数组的几倍。

此算法复制t n+k次的实例,其中k是排列中的循环数。您可以通过跳过p[i]=i的那些i,将其减少到最佳的拷贝数。

方法是遵循排列的“排列周期”,而不是从左到右索引数组。但是,由于必须从某个地方开始,每当需要新的排列周期时,搜索未经授权的元素都是从左到右的:

// Pseudo-code
N : integer, N > 0 // N is the number of elements
swaps : integer [0..N]
data[N] : array of object
permute[N] : array of integer [-1..N]  denoting permutation (used element is -1)
next_scan_start : integer;

next_scan_start  = 0;

    while (swaps < N )
    {
        // Search for the next index that is not-yet-permtued.  
        for (idx_cycle_search = next_scan_start; 
             idx_cycle_search < N;
             ++ idx_cycle_search)
            if (permute[idx_cycle_search] >= 0)
                break;

        next_scan_start = idx_cycle_search + 1;

        // This is a provable invariant.  In short, number of non-negative
        // elements in permute[] equals (N - swaps)
        assert( idx_cycle_search < N );

        // Completely permute one permutation cycle, 'following the
        // permutation cycle's trail'  This is O(N)
        while (permute[idx_cycle_search] >= 0)
        {
             swap( data[idx_cycle_search], data[permute[idx_cycle_search] )
             swaps ++;

             old_idx = idx_cycle_search;
             idx_cycle_search = permute[idx_cycle_search];
             permute[old_idx] = -1;  
             // Also '= -idx_cycle_search -1' could be used rather than '-1'
             // and would allow reversal of these changes to permute[] array
        }
    }

你的意思是你有一个对象数组o[1..n]然后你有一个数组p[1..n]包含数字1..n的排列,最后你想得到一个对象数组o1,使得所有k=1..n的o1[k]=o[p[k]]?

例如,如果您的对象是字母a、b、c…、y、z,并且您的数组p是[26、25、24、…、2、1]那么您想要的输出是z、y…、c、b、a吗?

如果是的话,我相信你可以用0(1)个额外的内存在线性时间内完成它。数组的反转元素是这种情况下的一种特殊情况。一般来说,我认为您需要考虑将置换p分解成循环,然后使用它来移动原始数组o[]的元素。

如果这就是你要找的,我可以详细说明。

编辑:其他人在我睡觉的时候已经提出了很好的解决方案,所以不需要在这里重复。^ ^ ^

编辑:我的O(1)附加空间确实不完全正确。我只考虑“数据”元素,但实际上,每个排列元素还需要存储一个位,所以如果我们是精确的,就需要额外的O(log n)位。但大多数时候使用符号位(如J.F.Sebastian所建议的)是很好的,所以在实践中我们可能不需要比我们已经拥有的更多的东西。

如果您不介意为额外的索引散列分配内存,那么可以保留原始位置到当前位置的映射,以获得接近o(n)的时间复杂性。这是Ruby中的一个例子,因为它是可读和伪代码的。(这可能比较短,也可能更惯用红宝石色,但为了清晰起见,我已经把它写了出来。)

#!/usr/bin/ruby

objects       = ['d', 'e', 'a', 'c', 'b']
order         = [2, 4, 3, 0, 1]
cur_locations = {}

order.each_with_index do |orig_location, ordinality|
  # Find the current location of the item.
  cur_location = orig_location
  while not cur_locations[cur_location].nil? do
    cur_location = cur_locations[cur_location]
  end

  # Swap the items and keep track of whatever we swapped forward.
  objects[ordinality], objects[cur_location] = objects[cur_location], objects[ordinality]
  cur_locations[ordinality] = orig_location
end

puts objects.join(' ')

这显然需要一些额外的散列内存,但是因为它只是用于索引,而不是用于“相当大”的对象,希望这是可以接受的。因为散列查询是O(1),即使由于一个项目被交换了不止一次,并且您必须重写的情况,复杂性也会略有增加。 cur_location 多次,算法作为一个整体应该合理地接近O(N)。

如果你想的话,你可以提前建立一个从原始到当前位置的完整哈希,或者保持从当前到原始的反向哈希,并稍微修改算法,使其严格降到O(N)。它会更复杂一些,占用更多的空间,所以这是我写的版本,但是修改不应该很困难。

编辑:事实上,我相当确定时间复杂性只是O(N),因为每个顺序最多可以有一个关联的跃点,因此查找的最大数量限制为N。

#!/usr/bin/env python

def rearrange(objects, permutation):
    """Rearrange `objects` inplace according to `permutation`.

       ``result = [objects[p] for p in permutation]``
    """
    seen = [False] * len(permutation)
    for i, already_seen in enumerate(seen):
        if not already_seen: # start permutation cycle
            first_obj, j = objects[i], i
            while True:
                seen[j] = True
                p = permutation[j]
                if p == i: # end permutation cycle
                    objects[j] = first_obj    # [old] p -> j
                    break
                objects[j], j = objects[p], p #       p -> j

算法(正如我在写它之后注意到的)与 @meriton's answer in Java .

这里有一个 test 代码功能:

def test():
    import itertools
    N = 9
    for perm in itertools.permutations(range(N)):
        L = range(N)
        LL = L[:]
        rearrange(L, perm)
        assert L == [LL[i] for i in perm] == list(perm), (L, list(perm), LL)

    # test whether assertions are enabled
    try:
        assert 0
    except AssertionError:
        pass
    else:
        raise RuntimeError("assertions must be enabled for the test")

if __name__ == "__main__":
    test()

有一个 histogram sort 尽管运行时间比O(n)(n日志n)高一点。

我可以在有O(N)划痕空间的情况下完成它——复制到新数组并复制回。

编辑:我知道将要进行的算法的存在。其思想是在1..n整数数组上执行交换,同时在大型对象数组上镜像交换。我现在找不到算法。

这个问题是在有最小O(1)额外存储的地方应用置换的问题之一:“原位置换”。

它 是 可解,但算法事先并不明显。

它被简单地描述为Knuth中的一个练习,对于工作,我必须破译它并弄清楚它是如何工作的。看5.2 13。

关于这个问题的一些更现代的研究,使用伪代码:

http://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/forschung/berichte/bericht_273.pdf

我最后为这个编写了一个不同的算法,它首先生成一个交换列表来应用一个订单,然后运行整个交换来应用它。其优点是,如果要对多个列表应用排序,则可以重用交换列表,因为交换算法非常简单。

void make_swaps(vector<int> order, vector<pair<int,int>> &swaps)
{
    // order[0] is the index in the old list of the new list's first value.
    // Invert the mapping: inverse[0] is the index in the new list of the
    // old list's first value.
    vector<int> inverse(order.size());
    for(int i = 0; i < order.size(); ++i)
        inverse[order[i]] = i;

    swaps.resize(0);

    for(int idx1 = 0; idx1 < order.size(); ++idx1)
    {
        // Swap list[idx] with list[order[idx]], and record this swap.
        int idx2 = order[idx1];
        if(idx1 == idx2)
            continue;

        swaps.push_back(make_pair(idx1, idx2));

        // list[idx1] is now in the correct place, but whoever wanted the value we moved out
        // of idx2 now needs to look in its new position.
        int idx1_dep = inverse[idx1];
        order[idx1_dep] = idx2;
        inverse[idx2] = idx1_dep;
    }
}

template<typename T>
void run_swaps(T data, const vector<pair<int,int>> &swaps)
{
    for(const auto &s: swaps)
    {
        int src = s.first;
        int dst = s.second;
        swap(data[src], data[dst]);
    }
}

void test()
{
    vector<int> order = { 2, 3, 1, 4, 0 };

    vector<pair<int,int>> swaps;
    make_swaps(order, swaps);

    vector<string> data = { "a", "b", "c", "d", "e" };
    run_swaps(data, swaps);
}