重複する要素を取り除く DouKaku?

与えられたリストxsの中から、 2回以上出現するものを全部取り除いてください。

サンプル入力
[3, 1, 4, 1, 5, 9, 2, 6, 5]
サンプル出力
[3, 4, 9, 2, 6]

これはアレイのuniqの派生問題です。リストとかアレイという言葉は言語によってまちまちの意味で使われているので、「配列のようなもの」という漠然とした意味にとって構いません。

def only_unique(ary)
  freq = ary.inject(Hash.new(0)){|h,x| h[x]+=1; h }
  ary.select{|x| freq[x]==1 }
end
only_unique([3, 1, 4, 1, 5, 9, 2, 6, 5]) # => [3, 4, 9, 2, 6]

1
2
3

(defun only-unique (list)
  (remove-if (lambda (x) (>= (count x list) 2)) list))
(only-unique '(3 1 4 1 5 9 2 6 5))      ; => (3 4 9 2 6)

要素がEqクラスのインスタンスなら

uniqOnly :: Eq a => [a] -> [a]
uniqOnly = uniq []
  where uniq xs [] = reverse xs
        uniq xs (y:ys) = case break (y ==) xs of
          (_,[])    -> uniq (y:xs) ys
          (ps,_:qs) -> uniq (ps++qs) ys

{-
uniqOnly [3,1,4,1,5,9,2,6,5]
[3,4,9,2,6]
-}

ああやっちゃった。お題を全然満たしてない！

こっちが正解のはず

uniqOnly :: Eq a => [a] -> [a]
uniqOnly = uniq [] []
  where uniq xs ys [] = reverse xs
        uniq xs ys (z:zs) = case break (z==) xs of
          (_,[]) | z `notElem` ys -> uniq (z:xs) ys zs
                 | otherwise      -> uniq xs ys zs
          (ps,_:qs)               -> uniq (ps++qs) (z:ys) zs

{-
*Main> uniqOnly [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]
[4,2,6,8,7]
-}

要素がOrdクラスのインスタンスなら、こちらの方が効率がいいはず

import Data.List

binapp :: (b -> b -> c) -> (a -> b) -> (a -> a -> c)
binapp o f x y = f x `o` f y
eqapp :: Eq b => (a -> b) -> (a -> a -> Bool)
eqapp = binapp (==) 
cmpapp :: Ord b => (a -> b) -> (a -> a -> Ordering)
cmpapp = binapp compare

mapFilter f p xs = [ f x | x <- xs, p x ]

lenOne [x] = True
lenOne _   = False

uniqOnly :: Ord a => [a] -> [a]
uniqOnly = map snd
         . sortBy (cmpapp fst) 
         . mapFilter head lenOne 
         . groupBy (eqapp snd) 
         . sortBy (cmpapp snd) 
         . zip [0..]

foldl を使う版

uniqOnly :: Eq a => [a] -> [a]
uniqOnly = reverse . fst . foldl uniq ([],[])
  where uniq (xs,ys) z = case break (z==) xs of
           (_,[]) | z `notElem` ys -> (z:xs,ys)
                  | otherwise      -> (xs,ys)
           (ps,_:qs)               -> (ps++qs,z:ys)

ああっ。寝惚けてる mapAccumL じゃなくて foldlだ！
御免なさい。タグまでうっちゃった。
import Data.List は不要です。

1	Dim uniq = From x In xs Group By x Into Count() Where Count = 1 Select x

速度的には、defaultdict より
h[i] = h.get(i, 0) + 1
のようなものを使ったほうが速いんでしょうけど・・・
可読性重視で。

import collections

def only_unique(a):
    h = collections.defaultdict(int)
    for i in a:
        h[i] += 1
    return [i for i in a if h[i] == 1]

def main():
    print only_unique([3, 1, 4, 1, 5, 9, 2, 6, 5])

if __name__ == '__main__':
    main()

uneval の無い環境とプロパティの順番が保証されない可能性に配慮したら，えらく冗長になってしまった。

function doukaku56(a){
  if(typeof uneval != 'function') var uneval = function(o){
    if(o === undefined) return 'undefined';
    if(o === null)      return 'null';
    var s = o.toString();
    switch(o.constructor){
     case Object:
      if(s.indexOf('[object Object')) return s;
      var m = []; for(var p in o) m[m.length] = p +':'+ arguments.callee(o[p]);
      return '({'+ m.join(', ') +'})';
     case Array:
      var a = []; for(var i = o.length; i--;) a[i] = arguments.callee(o[i]);
      return '['+ a.join(', ') +']';
     case String:
      return '"'+ s.replace(/[\"\\]/g,'\\$&').replace(/\r/g,'\\r').replace(/\n/g,'\\n') +'"';
     case Date: return '(new Date('+ +o +'))';
     default:   return s;
    }
  };
  var r = [], h = {}, k, i, l;
  for(i = 0, l = a.length; i < l; i++) h[k = uneval(a[i])] = k in h ? -1 : i;
  for(k in h) if(h[k] >= 0) r[r.length] = h[k];
  for(i = r.sort(function(x, y){ return x - y }).length; i--;) r[i] = a[r[i]];
  return r;
}

ふつうに。

import scala.collection.mutable.HashMap

def uniqOnly[A](a:Seq[A]) = {
  val map = a.foldLeft(new HashMap[A,int]){(r,v)=>r(v)=r.getOrElse(v,0)+1;r}
  a.filter(map(_)==1)
}

println(uniqOnly(Array(3, 1, 4, 1, 5, 9, 2, 6, 5)))

再帰再帰・・・。

pythonで再帰にこだわるのは間違っている気がするが。

def oneces(xs, duplicated=None):
  if duplicated is None:
    duplicated = []
  if len(xs) < 2:
    return xs
  o = oneces(xs[:-1], duplicated)
  if xs[-1] in duplicated:
    return o
  if xs[-1] in o:
    o.remove(xs[-1])
    duplicated.append(xs[-1])
    return o
  return o+xs[-1:]

PHPは配列操作得意ですね。

<?php
function only_unique($ary) {
	foreach ( $ary as $val ) {
		if ( count(array_keys($ary,$val)) == 1 ) {
			$rtn[] = $val;
		}
	}
	return $rtn;
}

print_r(only_unique(array(3, 1, 4, 1, 5, 9, 2, 6, 5)));
?>

Squeak Smalltalk で。

#occurrencesOf: は配列（array）にも適用できますが非効率なので、bag を介在させています。bag は内部的に要素を要素種と数で管理するコレクションです。

| array bag |
array := #(3 1 4 1 5 9 2 6 5).
bag := array asBag.
^array reject: [:each | (bag occurrencesOf: each) > 1]  "=> #(3 4 9 2 6) "

import java.util.*;

public class UniqOnly {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5);
		
		Set<Integer> counter = new HashSet<Integer>();
		Set<Integer> dup = new HashSet<Integer>();
		
		for (int i = 0, n = list.size(); i < n; i++) {
			if(!counter.add(list.get(i))) {
				dup.add(list.get(i));
			}
		}
		list = new LinkedList<Integer>(list);
		list.removeAll(dup);
		System.out.println(list);
	}
}

[x for x in xs if xs.count(x) == 1] から、
重複する値が多数あった場合を考えて、ループ回数を減らすために集合を利用。
最後は、 sorted(..., key=xs.index) で元の順番に並べ替え。

1 2	def only_uniq(xs): return sorted((x for x in set(xs) if xs.count(x) == 1), key=xs.index)

なら、もしかしてこれでいける？

1 2	def only_uniq(xs): return sorted(set(xs), key=xs.index)

ナイーブな実装。
% awk -f remove_multiples_1.awk
3 14 15 92 65 35 89 79 32 38 46 26 43 38 32 79
3 14 15 92 65 35 89 46 26 43 
cat lion tiger lion
cat tiger 
1  2  1  0
2 0

{
	xs_size = split($0,xs)
	remove_multiples(xs,xs_size)
	for (i=1;i<=result_size;i++) printf result[i] " " ; printf "\n"
}

function remove_multiples(xs,xs_size, i) # 結果は result[], result_size へ
{
	delete occurrence
	for (i=1;i<=xs_size;i++) occurrence[xs[i]]++

	delete result
	result_size = 0
	for (i=1;i<=xs_size;i++)
		if (occurrence[xs[i]] == 1) result[++result_size] = xs[i]
}

配列を使わずにremove_multiples_1.awkと（ほぼ）同じ動作をする版。
% awk -f remove_multiples_2.awk
3 14 15 92 65 35 89 79 32 38 46 26 43 38 32 79
3 14 15 92 65 35 89 46 26 43 
cat lion tiger lion
cat tiger 
1  2  1  0
2  0

{
	orig = $0
	while (match(orig,/[^ ]+/)) {
		item = substr(orig,RSTART,RLENGTH)
		if (occurence[item]++ > 0) gsub(item " *","")
		orig = substr(orig,RSTART+RLENGTH)
	}
	print
	delete occurence
}

それは2回以上出現する要素を取り除いていないですね。前の問題の解答としてならアリですね。

あ、お題を誤読してました。順序を保存したuniqではなく
要素がひとつだけのものを残すんですね。
上のコードにマイナス付けておいてください。

member二回で濾過してみました。

(defun uniq-only (lst)
  (remove-if (lambda (item)
	       (member item (cdr (member item lst))))
	     lst))

効率について曖昧に書いてしまったので補足です．

#2806のuniqOnlyでは最悪のケースでの計算オーダーではＯ(n log n)です．
#2805や#2807のuniqOnlyでは最悪のケースでの計算オーダーはＯ(n^2)です．

入力リストとして[1..10^4]周辺の値を与えて計算時間を比較するとわかります．

他の言語でも，集合やバッグを使う場合，入力リストの要素が順序決定できる
値でないと最悪の場合 O(n^2) の計算になるとだろうと想像しています．

ちゃんと計測してみたら、要素が多いときは
collections.defaultdict の方が速かったです。
# 一概にどちらが遅いとはいえない

>>> import collections
>>> collections
<module 'collections' (built-in)>

なるほど、collectionsはネイティブで書かれてますね。
「初期化のコストが少し高いけども、
多くのデータを扱うならcollectionsの方がよい」
ということかもしれませんね。

修正しておきました。

pythonを知らないので想像ですが、
#2827で言及したことと同じことがおこってるのでは？

念のため時間を計測して bag を介することの有無の影響をみてみました。非力なマシン（PowerPC 1GHz, OS X）なので、1e3 で(^_^;)。

結果の単位はミリ秒で、順に「bag 使用時（bag への変換時間も込み）」「bag 使用時（同、含まず）」「bag 不使用時」です。

| array bag millisecondsWithBag millisecondsWithBag2 millisecondsWioutBag |
array := (1 to: 1e3) asArray.

millisecondsWithBag := [
	bag := array asBag.
	array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

millisecondsWithBag2 := [
	array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

millisecondsWioutBag := [
	array reject: [:each | (array occurrencesOf: each) > 1]] timeToRun.

^{millisecondsWithBag. millisecondsWithBag2. millisecondsWioutBag}   "=> #(19 8 526) "

1e3だけでなく2e3と4e3などの複数のプロファイルデータをとると、
計算量の増加の程度がそれぞれの場合で想像できるのではないでしょうか。

PS C:\> $list = (3, 1, 4, 1, 5, 9, 2, 6, 5)
PS C:\> $list | %{$h=@{}} {$h[$_] += 1}
PS C:\> $list | %{if($h[$_] -eq 1) {$_}}
3
4
9
2
6

1
2
3

$list = (3, 1, 4, 1, 5, 9, 2, 6, 5)
$list | %{$h=@{}} {$h[$_] += 1}
$list | %{if($h[$_] -eq 1) {$_}}

集合+ソートを用いたものでは、Pythonでの僕の投稿 #2818 も、
最悪のケースでの計算量は指数オーダーでした。

ユニークな要素の数が多すぎると sortとcountで効率が落ちる。
効率考えたつもりが返って悪化した悪い例になってしまった（恥

STLを使用。

#include <iostream>
#include <iterator>
#include <algorithm>

template <typename ForwardIterator>
ForwardIterator only_unique(ForwardIterator beg, ForwardIterator end)
{
    while (beg != end)
    {
        ForwardIterator new_beg = beg; ++new_beg;

        ForwardIterator new_end = std::remove(new_beg, end, *beg);

        if (new_end != end) // removed some elements
        {
            end = std::copy(new_beg, new_end, beg); // remove *beg
        }
        else
        {
            beg = new_beg;
        }
    }

    return end;
}

int main()
{
    int a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    int* p = only_unique(a, a + sizeof(a) / sizeof(*a));

    std::copy(a, p, std::ostream_iterator<int>(std::cout, " "));
}

1	uniqOnly xs = [x \| [x]<-[[z \| z<-xs, z==y] \| y<-xs]]

引数の配列を書き換えて。

#include <stdio.h>

int only_uniq(int *a, int len) {
	int i, j, dup = -1;
	int n, skip;
	
	for (i = 0; i < len; i++) {
		for (j = i + 1; j < len; j++) {
			if (a[i] == a[j]) {	
				dup = i;
				i = len;
				break;
			}
		}
	}
	
	if (dup == -1) return len;
	skip = a[dup];
	
	for (i = dup + 1; i < len; i++) {
		if ((n = a[i]) == skip) continue;
		for (j = i + 1; j < len; j++) {
			if (a[j] == n) {
				a[i] = skip;
				a[j] = skip;
			}
		}
	}
	
	j = 0;
	for (i = 0; i < len; i++) {
		if (a[i] != skip) a[j++] = a[i];
	}

	return j;
}

int main() {
	int a[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };
	int i, len;
	
	len = only_uniq(a, sizeof(a) / sizeof(a[0]));
	
	for (i = 0; i < len - 1; i++) {
		printf("%d, ", a[i]);
	}
	if (len > 0) printf("%d\n", a[i]);
	
	return 0;
}

効率の話題に付いて、
PythonのCookbookのForumでも同じような話題があったので、こっちに返信付けます。

リンク先の内容は、Pythonでのunique関数のレシピで、
今回のお題では、リスト内の要素の型について特に指定はありませんでしたが、
ハッシュや集合を用いる場合に、リストの要素がunhashableの場合等にも言及があります。
# あと、リスト内包内の隠し変数を使うとか裏技っぽいことが・・・

see: Remove duplicates from a sequence

了解です。では、あらためて。

| array bag millisecondsWithBag millisecondsWithBag2 millisecondsWioutBag |
#(1e3 2e3 4e3) collect: [:size |

	array := (1 to: size) asArray.

	millisecondsWithBag := [
		bag := array asBag.
		array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

	millisecondsWithBag2 := [
		array reject: [:each | (bag occurrencesOf: each) > 1]] timeToRun.

	millisecondsWioutBag := [
		array reject: [:each | (array occurrencesOf: each) > 1]] timeToRun.

	size -> {millisecondsWithBag. millisecondsWithBag2. millisecondsWioutBag}]

"=> {1000->#(19 8 548) . 2000->#(43 19 2169) . 4000->#(82 38 8725)} "

むむ、一瞬何が起きているのかと思いました。
xs内の各要素yについて、「xsから値がyであるものだけを取り出したリスト」を作って
([3, 1, 4, 1 5]だったら[[3], [1, 1], [4], [1, 1], [5]])
その中から[x]の形のものだけを取り出している？？
Haskellのリスト内包ってパターンマッチもやって、
マッチしない場合は捨ててくれるのかな？

> Haskellのリスト内包ってパターンマッチもやって、
> マッチしない場合は捨ててくれるのかな？

yes

効率はO(n^2)ですが、niceなコードですね。

パターンマッチがうらやましい…

DouKaku?

重複する要素を取り除く

Posted feedbacks - Flatten