200

セットからランダムな要素を選択するにはどうすればよいですか? Java で、HashSet または LinkedHashSet からランダムな要素を選択することに特に興味があります。他の言語のソリューションも大歓迎です。

4

34 に答える 34

98
int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
    if (i == item)
        return obj;
    i++;
}
于 2008-09-24T00:17:08.267 に答える
76

やや関連性のあるご存知ですか:

java.util.Collectionsコレクション全体をシャッフルするための便利な方法があります:Collections.shuffle(List<?>)およびCollections.shuffle(List<?> list, Random rnd)

于 2008-09-24T00:43:03.633 に答える
37

ArrayListおよびHashMap: [要素 -> インデックス]を使用した Java の高速ソリューション。

動機:RandomAccess特にセットからランダムなアイテムを選択するために、プロパティを持つアイテムのセットが必要でした (pollRandomメソッドを参照)。バイナリ ツリーのランダム ナビゲーションは正確ではありません。ツリーは完全にバランスが取れていないため、均一な分布にはなりません。

public class RandomSet<E> extends AbstractSet<E> {

    List<E> dta = new ArrayList<E>();
    Map<E, Integer> idx = new HashMap<E, Integer>();

    public RandomSet() {
    }

    public RandomSet(Collection<E> items) {
        for (E item : items) {
            idx.put(item, dta.size());
            dta.add(item);
        }
    }

    @Override
    public boolean add(E item) {
        if (idx.containsKey(item)) {
            return false;
        }
        idx.put(item, dta.size());
        dta.add(item);
        return true;
    }

    /**
     * Override element at position <code>id</code> with last element.
     * @param id
     */
    public E removeAt(int id) {
        if (id >= dta.size()) {
            return null;
        }
        E res = dta.get(id);
        idx.remove(res);
        E last = dta.remove(dta.size() - 1);
        // skip filling the hole if last is removed
        if (id < dta.size()) {
            idx.put(last, id);
            dta.set(id, last);
        }
        return res;
    }

    @Override
    public boolean remove(Object item) {
        @SuppressWarnings(value = "element-type-mismatch")
        Integer id = idx.get(item);
        if (id == null) {
            return false;
        }
        removeAt(id);
        return true;
    }

    public E get(int i) {
        return dta.get(i);
    }

    public E pollRandom(Random rnd) {
        if (dta.isEmpty()) {
            return null;
        }
        int id = rnd.nextInt(dta.size());
        return removeAt(id);
    }

    @Override
    public int size() {
        return dta.size();
    }

    @Override
    public Iterator<E> iterator() {
        return dta.iterator();
    }
}
于 2011-04-14T20:06:48.913 に答える
32

Java 8 では:

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}
于 2018-07-19T01:15:32.860 に答える
16

Java で実行する場合は、要素をある種のランダム アクセス コレクション (ArrayList など) にコピーすることを検討する必要があります。セットが小さい場合を除き、選択した要素へのアクセスは高価になるためです (O(1) ではなく O(n))。[編集: リストのコピーも O(n)]

または、要件により厳密に一致する別の Set 実装を探すこともできます。Commons CollectionsのListOrderedSetは有望に見えます。

于 2008-09-24T19:38:30.237 に答える
9

Java の場合:

Set<Integer> set = new LinkedHashSet<Integer>(3);
set.add(1);
set.add(2);
set.add(3);

Random rand = new Random(System.currentTimeMillis());
int[] setArray = (int[]) set.toArray();
for (int i = 0; i < 10; ++i) {
    System.out.println(setArray[rand.nextInt(set.size())]);
}
于 2008-09-24T00:16:32.073 に答える
8
List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);
于 2012-12-04T22:18:05.157 に答える
3

Clojureソリューション:

(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))
于 2008-12-23T03:51:32.583 に答える
2

Perl 5

@hash_keys = (keys %hash);
$rand = int(rand(@hash_keys));
print $hash{$hash_keys[$rand]};

これを行う1つの方法があります。

于 2008-09-24T00:51:41.397 に答える
2

C++. セット全体を反復処理したり並べ替えたりする必要がないため、これはかなり高速です。これは、 tr1をサポートしていると仮定すると、ほとんどの最新のコンパイラでそのまま使用できるはずです。そうでない場合は、Boost を使用する必要があるかもしれません。

Boost ドキュメントは、Boost を使用しない場合でも、これを説明するのに役立ちます。

秘訣は、データがバケットに分割されているという事実を利用し、ランダムに選択されたバケットを (適切な確率で) すばやく識別することです。

//#include <boost/unordered_set.hpp>  
//using namespace boost;
#include <tr1/unordered_set>
using namespace std::tr1;
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;

int main() {
  unordered_set<int> u;
  u.max_load_factor(40);
  for (int i=0; i<40; i++) {
    u.insert(i);
    cout << ' ' << i;
  }
  cout << endl;
  cout << "Number of buckets: " << u.bucket_count() << endl;

  for(size_t b=0; b<u.bucket_count(); b++)
    cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl;

  for(size_t i=0; i<20; i++) {
    size_t x = rand() % u.size();
    cout << "we'll quickly get the " << x << "th item in the unordered set. ";
    size_t b;
    for(b=0; b<u.bucket_count(); b++) {
      if(x < u.bucket_size(b)) {
        break;
      } else
        x -= u.bucket_size(b);
    }
    cout << "it'll be in the " << b << "th bucket at offset " << x << ". ";
    unordered_set<int>::const_local_iterator l = u.begin(b);
    while(x>0) {
      l++;
      assert(l!=u.end(b));
      x--;
    }
    cout << "random item is " << *l << ". ";
    cout << endl;
  }
}
于 2010-07-20T13:45:31.713 に答える
2

上記のソリューションはレイテンシーの観点から述べていますが、各インデックスが選択される確率が等しいことを保証するものではありません。
それを考慮する必要がある場合は、リザーバー サンプリングを試してください。http://en.wikipedia.org/wiki/Reservoir_sampling
Collections.shuffle() (いくつかの提案による) は、そのようなアルゴリズムの 1 つを使用します。

于 2014-12-08T07:03:09.133 に答える
1

Lispで

(defun pick-random (set)
       (nth (random (length set)) set))
于 2008-09-24T04:28:29.457 に答える
1

Javascriptソリューション;)

function choose (set) {
    return set[Math.floor(Math.random() * set.length)];
}

var set  = [1, 2, 3, 4], rand = choose (set);

または代わりに:

Array.prototype.choose = function () {
    return this[Math.floor(Math.random() * this.length)];
};

[1, 2, 3, 4].choose();
于 2008-09-24T00:35:18.223 に答える
1

Iconにはセット型とランダム要素演算子である単項 "?" があるため、式は

? set( [1, 2, 3, 4, 5] )

1 から 5 までの乱数を生成します。

プログラムの実行時に乱数シードは 0 に初期化されるため、実行ごとに異なる結果を生成するには、randomize()

于 2008-09-24T01:46:43.247 に答える
1

ちょうどどうですか

public static <A> A getRandomElement(Collection<A> c, Random r) {
  return new ArrayList<A>(c).get(r.nextInt(c.size()));
}
于 2012-12-18T21:06:08.993 に答える
1

Mathematica では:

a = {1, 2, 3, 4, 5}

a[[ ⌈ Length[a] Random[] ⌉ ]]

または、最近のバージョンでは、単純に:

RandomChoice[a]

おそらく説明が不足しているため、これは反対票を投じられました。

Random[]0 と 1 の間の疑似乱数浮動小数点数を生成します。これにリストの長さを乗算し、天井関数を使用して次の整数に切り上げます。次に、このインデックスが から抽出されaます。

ハッシュテーブル機能はMathematica のルールで頻繁に行われ、ルールはリストに保存されるため、次を使用できます:

a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};
于 2011-04-15T23:14:41.527 に答える
1

Guavaを使用すると、Khoth の答えよりも少し良いことができます。

public static E random(Set<E> set) {
  int index = random.nextInt(set.size();
  if (set instanceof ImmutableSet) {
    // ImmutableSet.asList() is O(1), as is .get() on the returned list
    return set.asList().get(index);
  }
  return Iterables.get(set, index);
}
于 2016-04-28T15:22:01.443 に答える
1

「他の言語のソリューションも大歓迎です」とおっしゃっていたので、Python のバージョンは次のとおりです。

>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4
于 2008-09-24T00:15:45.023 に答える
1

セット/配列のサイズ/長さを取得し、0 とサイズ/長さの間の乱数を生成し、インデックスがその数と一致する要素を呼び出すことはできませんか? HashSet には .size() メソッドがあります。

疑似コードで -

function randFromSet(target){
 var targetLength:uint = target.length()
 var randomIndex:uint = random(0,targetLength);
 return target[randomIndex];
}
于 2008-09-24T00:18:46.077 に答える
1

PHP、「set」が配列であると仮定すると、次のようになります。

$foo = array("alpha", "bravo", "charlie");
$index = array_rand($foo);
$val = $foo[$index];

Mersenne Twister 関数の方が優れていますが、PHP には array_rand に相当する MT はありません。

于 2008-09-24T00:19:08.043 に答える
1

C# の場合

        Random random = new Random((int)DateTime.Now.Ticks);

        OrderedDictionary od = new OrderedDictionary();

        od.Add("abc", 1);
        od.Add("def", 2);
        od.Add("ghi", 3);
        od.Add("jkl", 4);


        int randomIndex = random.Next(od.Count);

        Console.WriteLine(od[randomIndex]);

        // Can access via index or key value:
        Console.WriteLine(od[1]);
        Console.WriteLine(od["def"]);
于 2008-09-24T03:32:31.383 に答える
1

Java 8 で最も簡単なのは次のとおりです。

outbound.stream().skip(n % outbound.size()).findFirst().get()

ここnで、 はランダムな整数です。もちろん、それはそれよりもパフォーマンスが低くなりますfor(elem: Col)

于 2015-02-24T20:20:06.930 に答える
0

PHP、MTを使用:

$items_array = array("alpha", "bravo", "charlie");
$last_pos = count($items_array) - 1;
$random_pos = mt_rand(0, $last_pos);
$random_item = $items_array[$random_pos];
于 2008-09-24T00:28:40.873 に答える
0

Khothの回答を出発点として使用する一般的なソリューション。

/**
 * @param set a Set in which to look for a random element
 * @param <T> generic type of the Set elements
 * @return a random element in the Set or null if the set is empty
 */
public <T> T randomElement(Set<T> set) {
    int size = set.size();
    int item = random.nextInt(size);
    int i = 0;
    for (T obj : set) {
        if (i == item) {
            return obj;
        }
        i++;
    }
    return null;
}
于 2015-03-27T10:52:44.437 に答える
0

残念ながら、これはどの標準ライブラリ セット コンテナーでも (O(n) よりも) 効率的に実行できません。

ランダム化されたピック関数をバイナリセットと同様にハッシュセットに追加するのは非常に簡単なので、これは奇妙です。スパースでないハッシュ セットでは、ヒットするまでランダムなエントリを試すことができます。二分木の場合、最大 O(log2) ステップで、左または右のサブツリーからランダムに選択できます。以下の後半のデモを実装しました。

import random

class Node:
    def __init__(self, object):
        self.object = object
        self.value = hash(object)
        self.size = 1
        self.a = self.b = None

class RandomSet:
    def __init__(self):
        self.top = None

    def add(self, object):
        """ Add any hashable object to the set.
            Notice: In this simple implementation you shouldn't add two
                    identical items. """
        new = Node(object)
        if not self.top: self.top = new
        else: self._recursiveAdd(self.top, new)
    def _recursiveAdd(self, top, new):
        top.size += 1
        if new.value < top.value:
            if not top.a: top.a = new
            else: self._recursiveAdd(top.a, new)
        else:
            if not top.b: top.b = new
            else: self._recursiveAdd(top.b, new)

    def pickRandom(self):
        """ Pick a random item in O(log2) time.
            Does a maximum of O(log2) calls to random as well. """
        return self._recursivePickRandom(self.top)
    def _recursivePickRandom(self, top):
        r = random.randrange(top.size)
        if r == 0: return top.object
        elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a)
        return self._recursivePickRandom(top.b)

if __name__ == '__main__':
    s = RandomSet()
    for i in [5,3,7,1,4,6,9,2,8,0]:
        s.add(i)

    dists = [0]*10
    for i in xrange(10000):
        dists[s.pickRandom()] += 1
    print dists

出力として [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] が得られたので、分布は良好です。

私自身も同じ問題に苦しんできましたが、このより効率的な選択によるパフォーマンスの向上が、Python ベースのコレクションを使用するオーバーヘッドに見合う価値があるかどうかはまだ判断していません。もちろん、それを洗練してCに翻訳することもできますが、それは今日の私にとっては大変な作業です:)

于 2009-12-27T00:13:39.323 に答える
0

セットを配列に転送して配列を使用することもできます。おそらく小規模で機能します。最も投票された回答の for ループはとにかく O(n) です

Object[] arr = set.toArray();

int v = (int) arr[rnd.nextInt(arr.length)];
于 2014-11-11T19:43:58.540 に答える
0

ランダム性を保証せずに、本当に「任意の」オブジェクトを選択したい場合はSet、イテレータによって最初に返されたものを取得するのが最も簡単です。

    Set<Integer> s = ...
    Iterator<Integer> it = s.iterator();
    if(it.hasNext()){
        Integer i = it.next();
        // i is a "random" object from set
    }
于 2015-02-04T15:50:10.963 に答える
0

サードパーティのライブラリを気にしない場合、Utilsライブラリには、Set を受け取り、そこからランダムな要素を返す randomFrom(Iterable iterable) メソッドを持つ IterableUtils があります

Set<Object> set = new HashSet<>();
set.add(...);
...
Object random = IterableUtils.randomFrom(set);

次の Maven 中央リポジトリにあります。

<dependency>
  <groupId>com.github.rkumsher</groupId>
  <artifactId>utils</artifactId>
  <version>1.3</version>
</dependency>
于 2017-08-07T23:05:33.803 に答える
-1

セットサイズが大きくない場合は、配列を使用してこれを行うことができます。

int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];
于 2016-01-04T15:10:55.023 に答える
-2

このスレッドを読んだ後、私が書くことができる最高のものは次のとおりです。

static Random random = new Random(System.currentTimeMillis());
public static <T> T randomChoice(T[] choices)
{
    int index = random.nextInt(choices.length);
    return choices[index];
}
于 2011-03-02T02:06:33.087 に答える