仲間はずれの判定 in Python DouKaku?

仲間はずれの判定

リストxsが渡されたときに

全部の要素が同じ値である(例：[1, 1, 1, 1])、
一つだけ仲間はずれがある(例：[1, 2, 1, 1, 1])、
その他

を識別する関数を作ってください。また判定後に「全部の要素が同じ値」の場合にはその値、「一つだけ仲間はずれがある」の場合にはその仲間はずれの値と多数派の値を複雑な処理なしに取得できるようにしてください。

型にうるさい言語のために：リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。

追記：リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。

もっとスリム化できそうですがとりあえず。

import java.util.*;
public class NakamaHazure {
    public static void main(String[] args) {
        check(Arrays.asList(1,1,1,1));    // => [1]
        check(Arrays.asList(1,2,1,1,1));    // => [2,1]
        check(Arrays.asList(1,2,2,1,1));    // => []
        check(Arrays.asList(1,2,2,1,3));    // => []
    }
    private static void check(List<Integer> list) {
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> minor = new HashSet<Integer>();;
        Integer major = null;
        for (Integer i : list) {
            if (!set.add(i)) {
                if (major != null && major != i) {
                    System.out.println("[]");
                    return;
                }
                minor.remove(i);
                major = i;
            } else {
                minor.add(i);
            }
        }
        if (set.size() == 1) {
            System.out.println("[" + set.iterator().next() + "]");
        } else if (set.size() == 2) {
            System.out.println("[" + minor.iterator().next() + "," + major + "]");
        } else {
            System.out.println("[]");
        }
    }
}

array_count_values便利ですね。あえて使わないで作ってみる事で便利さを際実感

$a[]= array(1,1,1,1);#1
$a[]= array(1,2,1,1,1);#2
$a[]= array(2,1,2,2);#その他
$a[]= array(1,2,2,2);#その他
$a[]= array(1,1,2,2);#その他
$a[]= array(1,1,2,3);#その他
function check($_array){
    $uniques = sizeof(array_unique($_array));
    switch($uniques){
        case(1):
            return array("仲間"=>array_pop($_array));
        case(2):
            sort($_array);
            #仲間はずれ
            if( $_array[0]!=$_array[1] ){
                return array( "仲間はずれ"=>array_shift($_array),"仲間"=>array_pop($_array) );
            }else if($_array[0]==$_array[1] && $_array[sizeof($_array)-1] != $_array[sizeof($_array)-2] ){
                return array( "仲間はずれ"=>array_pop($_array),"仲間"=>array_shift($_array) );
            }
        default:
            return "その他";
    }


}

foreach( $a as $b ){
    print_r( check($b) ).PHP_EOL;
}

post comment

Posted feedbacks - Python

ディクショナリ使ってる。
ちょっと頭悪い実装。
すべて同じ時 0、一個違うとき1、その他2を返します。

def check(xs):
    c = {}
    for i in xs:
        if not c.has_key(i):
            c[i] = 0
        c[i] += 1
        if (len(c) == 3):
            return 2

    if len(c) == 1:
        return 0
    if len(c) == 2:
        a = c.items()[0][1]
        b = c.items()[1][1]
        if min(a,b) > 1:
            return 2
        return 1
    else:
        return 2
        

print check((1,1,1,1))
print check((1,1,1,2))
print check((1,1,2,1))
print check((1,1,2,3))
print check((1,2,2,1))
print check((1,2,2,1))

まだまだ感が否めない。。。

def lookfor(target):
    count = {}
    for v in target:
        if not count.has_key(v):
            count[v] = target.count(v)
    #2つ以上要素があって、1回出現の要素がない時はその他
    #要素が2つより多い場合もその他
    if (1 not in count.values() and len(count.keys()) >= 2)\
            or len(count.keys()) > 2:
        print '%s その他' % (target)
    #要素が1つしかない時は全部同じ
    elif len(count.keys()) == 1:
        print '%s 全て同じ' % (target)
    #この時点で1回出現の要素と多数出現の要素の2つが残っている
    else:
        for k, v in count.iteritems():
            if v == 1:
                outofgroup = k
            else:
                group = k
        print '%s 多数派: %s, 仲間外れ: %s' % (target, group, outofgroup)

以下を返値とする。
全部の要素が同じ値である： 1
一つだけ仲間はずれがある： 2
その他： 0

また、dup_check.majorとdup_check.minorで必要な値を取り出せる。

try: set
except NameError: from sets import Set as set

def dup_check(xs):
	for attr in ['major', 'minor']:
		if hasattr(dup_check, attr): delattr(dup_check, attr)
	L = list(set(xs))
	if len(L) == 1:
		dup_check.major = L[0]
		return 1
	elif len(L) == 2:
		L.sort(key=xs.count)
		dup_check.minor = L[0]
		dup_check.major = L[1]
		return 2
	else:
		return 0

print 'ret =', dup_check([1,1,1,1])
print 'uniq =', dup_check.major
print
print 'ret =', dup_check([1,2,1,1,1])
print 'major =', dup_check.major
print 'minor =', dup_check.minor
print
print 'ret =', dup_check([1,2,3,4])

出力：
ret = 1
uniq = 1

ret = 2
major = 1
minor = 2

ret = 0

戻り値は2要素のタプルを返す
　(その要素, None)　ー　要素が全部同じの時
　(多い方の要素, 少ない方の要素)　ー　要素が一つだけのものと他全部同じの時
　(None, None)　ー　それ以外の場合

def f(xs):
  a = list(set(xs))
  if len(a) == 1: return xs[0], None
  if len(a) == 2 and xs.count(a[0]) == 1: return a[1], a[0]
  if len(a) == 2 and xs.count(a[1]) == 1: return a[0], a[1]
  return None, None

print f([1,1,1,1])
print f([1,2,1,1,1])
print f([1,1,2,2])
print f([1,1,2,3])

xsの集合を、xs内に含まれる数をキーにソートします。
各条件は、戻り値の要素数で判断。

1	f=lambda xs: sorted(set(xs), key=xs.count)

戻り値は #2633 と同じです。

def f(xs):
　　return (lambda s: ((s[0],None) if len(s) == 1 else 
                     (s[1],s[0]) if len(s) == 2 and xs.count(s[0]) == 1 else
                     (None, None)))(sorted(set(xs), key=xs.count))

「sorted(set(xs), key=xs.count)を使って出現回数でソートする」という発想はいいアイデアだと思うのでプラス評価したいのですけど… ちょっとこのコードにプラス評価をつけるのはためらわれます…。

というわけで読みやすく書き直してみました。

def f(xs):
	s = sorted(set(xs), key=xs.count)
	if len(s) == 1:
		return (s[0], None)
	elif len(s) == 2:
		if xs.count(s[0]) == 1:
			return (s[1], s[0])
	return (None, None)

もしlambdaにこだわりがあるのでしたらこんな感じでどうでしょう。
141バイトです。xsを1文字に変えれば後3文字縮みますね。

>>> f([1,1,1,1,1,2])
(1, 2)
>>> f([1,2,1,1,1,1])
(1, 2)
>>> f([1,2,1,1,1,2,1])
(None, None)
>>> f([1,2,1,1,1,3,1])
(None, None)
>>> f([1,1,1,1,1])
(1, None)

1	f=lambda xs,N=None:(lambda k=xs.count:lambda s=sorted(set(xs),key=k):1==len(s)and(s[0],N)or 2==len(s)and 1==k(s[0])and(s[1],s[0])or(N,N))()()

最初は集合のソートだけで出来るかなと思ってたのに、お題を勘違いしてました。
順序が必要な時の要素数は２つだけなので、max,minで足りたかな。

snippet:

# リストの中から出現頻度の低い値を取り出し。
min(xs, key=xs.count)

# 仲間外れ(１つだけの要素)がいる
1 in map(xs.count,set(xs))

DouKaku?

仲間はずれの判定

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq