4

It looks like I can't either use an ArrayList nor a Set:

  • Set<> - I can avoid duplicates using a set, but no shuffle option // Collections.shuffle(List<?> list)

  • ArrayList<> - I can use shuffle to randomise the list, but duplicates are allowed.

I could use a Set and convert this into an ArrayList (or the other way around) to avoid the duplicates. Alternatively, loop through the set to randomise the items. But I am looking for something more efficient.

gd1
  • 11,300
  • 7
  • 49
  • 88
BLuEGoD
  • 251
  • 3
  • 11
  • You could check if the item is already in the ArrayList, before adding it: myList.contains(myItem); This check should only be O(n). – HectorLector Feb 15 '13 at 10:56
  • 4
    *something more efficient* > Are you saying this because you've (a) tried it, and (b) have concluded, through appropriate benchmarking, that this is a significant bottleneck in your application? If not, don't prematurely optimise and write whichever version reads most clearly (probably convert to arraylist). – Duncan Jones Feb 15 '13 at 10:57

5 Answers5

3

You can maintain two separate collections, an ArrayList and a HashSet, and reject insertion of any item which is present in the HashSet.

If you are concerned with encapsulation, wrap the two collections in a meta-object that implements List, and carefully document that insertions of duplicate elements will be rejected, even if the general contract of List doesn't prescribe so.

Talking about the cost of this solution, I believe that in terms of time the cost would be absolutely negligible if compared to a plain ArrayList: most operations on HashSets cost amortized O(1), namely lookup and insertion. On the other hand, your memory usage will be twice (or more, depending on the HashSet load factor).

gd1
  • 11,300
  • 7
  • 49
  • 88
  • Based on your comment on my answer, your solution is probably best. But I would mention the O(1) duplicate checking. – Duncan Jones Feb 15 '13 at 11:04
  • It is somewhat controversial. Insertions in a HashSet may cost O(n) in some circumstances. However I added it. – gd1 Feb 15 '13 at 11:04
  • 2
    You could also implement Set instead and create an iterator that returns the elements in random order I suppose. – Maarten Bodewes Feb 15 '13 at 11:07
  • @owlstead: I see, but this will break Collections.shuffle() and clients may rely on it. It depends on the whole scenario. – gd1 Feb 15 '13 at 11:08
  • That's a good point gd1, it may be tricky to implement this without being able to use `Collections.shuffle()` on the proprietary `Set` implementation. – Maarten Bodewes Feb 15 '13 at 11:32
1

As far as I know sets aren't ordered, so you obviously cannot shuffle items of sets. For removing duplicates from a list I found this: How do I remove repeated elements from ArrayList?.

Community
  • 1
  • 1
qben
  • 813
  • 10
  • 22
0

With the least amount of code and most elegance you can do something like:

 public void testFoo() {
    Set<Integer> s = new TreeSet<Integer>();

    s.add(2);
    s.add(1);
    s.add(3);

    Collections.shuffle(Arrays.asList(s.toArray()));
}

But this is not very effective, you could use an array and a hash function to put the elements in the desired spot on the array, and check of they are already there before putting them, this will work in O(n) time, so it's very good, but needs a little more code and some attention to the hash function.

comanitza
  • 1,103
  • 2
  • 10
  • 17
0
  • You can use a Map to avoid duplicates and then Map.entrySet() and shuffle the ArrayList
pablo pidal
  • 349
  • 4
  • 4
0

You could actually use an "ordered set", e.g. TreeSet. In order to get a random order, don't insert the actual item but a wrapper with some random weight and use a corresponding comparator. Re-shuffling however would require to update all wrapper weights.

gnomie
  • 439
  • 5
  • 16