1

与えられたマルチセットを仮定しましょう、例えば

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

そのような要素をソートする最も簡単な方法は何ですか:

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

つまり、セットの利用可能な要素から構築された昇順のサブシーケンスから構築されたシーケンス?

C++ と Python の両方で達成する方法。そのためのライブラリはありますか？「手で」それを行う方法は？

4

7 に答える 7

2

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]]

ネストされたリストを取得したら、 izip_longestgroupsを使用してマトリックスを反転し、リストを平坦化し、値を削除します。None

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

版画

[1, 2, 3, 1, 2, 3, 1, 3]
于 2013-10-31T19:22:42.530 に答える
2

これをCounting ソートとして実装できます 。まず、各要素が何回出現するかをカウントします。要素は、各値の出現回数を格納する配列内のインデックスです。次に、各インデックスの値がゼロになるまで、その配列をループします。

これは実装するのに最適な (または最も効率的な) 方法ではないかもしれませんが、最初に頭に浮かぶのはこの解決策です。

于 2013-10-31T18:50:59.220 に答える
1 
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]
于 2013-10-31T20:11:06.537 に答える
1

2 番目のシーカンシャル コンテナーを使用する場合、C++ では、標準アルゴリズム std::unique_copy および std::set_difference を使用して、元のコンテナーの要素を 2 番目のコンテナーに単純に移動できます。

于 2013-10-31T19:57:01.670 に答える
1

インポートされたライブラリなしで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]
于 2013-10-31T19:27:32.630 に答える
1

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);
}
于 2013-11-01T05:55:57.110 に答える