按照升序子序列排序多重集，每個可用元素髮生一次

Question

假設給定多重集，例如，

A = {1, 1, 1, 2, 2, 3, 3, 3}. 

什麼是這樣的元素進行排序的最簡單的方法：

(1, 2, 3, 1, 2, 3, 1, 3), 

即一個從上升從一組可用的元素，內置內置亞序列？

如何在C++和Python中實現。有沒有任何圖書館？如何「手工」呢？

Answer 1

您可以將其實現爲Counting sort 首先計算每個元素出現的次數，元素是數組中存儲每個值出現次數的索引。然後遍歷該數組，直到每個索引的值爲零。

這可能不是實現它的最好（或最有效）的方式，但這是首先想到的解決方案。

Answer 2

假設你願意修改原來的多集，（或工作在它的一個副本），這樣做

while(!data.empty()) { 
    auto x = data.begin(); 
    while(x != data.end()) { 
     auto value = *x; 
     cout << value << endl; 
     data.erase(x); // delete *one* item 
     x = data.upper_bound(value); // find the next *different* value 
    } 
} 

這是不是很有效。如果你有一個龐大的數據集，那麼你可能需要考慮一下你的約束條件（記憶或時間？）。

Answer 3

在Python中，你可以使用groupby從排序列表獲取項目的獨特羣體的矩陣：

from itertools import groupby, izip_longest 

A=[1, 1, 1, 2, 2, 3, 3, 3] 

groups=[] 
for k, g in groupby(sorted(A)): 
    groups.append(list(g)) 

print groups 
# [[1, 1, 1], [2, 2], [3, 3, 3]] 

更簡潔，您可以使用列表中理解到做同樣的事情：

groups=[list(g) for _, g in groupby(sorted(A))] 
# [[1, 1, 1], [2, 2], [3, 3, 3]] 

或者，你可以展開一個多集，Counter的Python版本，並且鍵排序，以獲得此相同的嵌套列表：

from collections import Counter 
c=Counter(A) 
groups=[[k]*c[k] for k in sorted(c.keys())] 
# [[1, 1, 1], [2, 2], [3, 3, 3]] 

一旦你的嵌套列表groups，顛倒使用izip_longest矩陣，扁平化的列表，並刪除None值：

print [e for t in izip_longest(*groups) for e in t if e!=None] 

打印

[1, 2, 3, 1, 2, 3, 1, 3] 

Answer 4

這裏是如何用手做python沒有任何導入的庫：

A = (1, 1, 1, 2, 2, 3, 3, 3) 

# create a list out of a set of unique elems in A 
a = list(set(A)) 
a.sort() # sort so they are in ascending order 

countList = [] 

# find how many repeated elems in the list set we just made 
for i, elem in enumerate(a, 0): 
    countList.append(A.count(elem)) 

# find the what is the lowest repeated number in the orig list 
minEntry = min(countList) 
# we can multiply the list set by that lowest number 
outString = a * minEntry 

# add the left over numbers to the outstring 
for i in range(len(countList)): 
    count = abs(countList[i] - minEntry) 
    if count != 0: 
     outString.append(a[i]*count) 

print outString 

這裏是outputString

[1, 2, 3, 1, 2, 3, 1, 3] 

Answer 5

如果可以使用第二sequantial容器然後在C++中可以簡單地通過標準算法的std ::手段unique_copy和std :: set_difference移動至原來的容器的元件在第二容器中。

Answer 6

def Test(seq): 
    index = 0 
    Seq = seq 
    newlist = [] 
    while len(Seq) != 0: 
      newlist.append(list(set(Seq).union())) 
      for Del in newlist[index]: 
        Seq.remove(Del) 
      index += 1 
    return [y for x in newlist for y in x] 

Answer 7

在C++

，而不是操縱數據結構，你可以準備迭代器的列表，以平等的範圍的開端，進而再解引用/遞增的迭代器：

#include <set> 
#include <list> 
#include <iostream> 

int main() 
{ 
    std::multiset<int> A = {1, 1, 1, 2, 2, 3, 3, 3}; 

    // build a list of iterator pairs to each equal range 
    std::list< std::pair<std::multiset<int>::iterator, 
         std::multiset<int>::iterator> > iters; 
    for(auto it=A.begin(); it != A.end(); it = A.upper_bound(*it)) 
     iters.push_back(A.equal_range(*it)); 

    // for each non-empty subrange, show what the first iterator is 
    // pointing to, then advance it by one position in its subrange 
    // if the subrange is empty, drop it from the list 
    while(!iters.empty()) 
     for(auto it = iters.begin(); it != iters.end();) 
      if(it->first != it->second) 
       std::cout << *it++->first++ << ' '; // don't do this at home 
      else 
       it = iters.erase(it); 
}