Remove every 3rd element in arraylist

Question

I am trying to loop through an arraylist and gradually remove an element every 3 indices. Once it gets to the end of the arraylist I want to reset the index back to the beginning, and then loop through the arraylist again, again removing an element every 3 indices until there is only one element left in the arraylist.

The listOfWords is an array with a length of 3 that was previously filled.

int listIndex = 0;

do
{           
    // just to display contents of arraylist    
    System.out.println(listOfPlayers);

    for(int wordIndex = 0; wordIndex < listOfWords.length; wordIndex++
    {
        System.out.print("Player");
        System.out.print(listOfPlayers.get(wordIndex));
        System.out.println("");
        listIndex = wordIndex;                                  
    }           

    listOfPlayers.remove(listOfPlayers.get(listIndex)); 
}
while(listOfPlayers.size() > 1);

I have tried to implement for several hours yet I am still having trouble. Here's what happens to the elements of the arraylist:

1, 2, 3, 4

1, 2, 4

1, 2

Then it throws an 'index out of bounds error' exception when it checks for the third element (which no longer exists). Once it reaches the last element I want it to wrap around to the first element and continue through the array. I also want it to start where it left off and not from the beginning once it removes an element from the arraylist.

Answer 1

Try the following code. It keeps on removing every nth element in List until one element is left.

    List<Integer> array = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
    int nth = 3;
    int step = nth - 1;
    int benchmark = 0;

    while (array.size() > 1) {
        benchmark += step;
        benchmark = benchmark > array.size() - 1 ? benchmark % array.size() : benchmark;
        System.out.println(benchmark);
        array.remove(array.get(benchmark));
        System.out.println(array);
    }

Answer 2

Maybe I have just missed the boat, but is this what you were after?

import java.util.ArrayList;
import java.util.Random;

public class Test {

    public static void main(String[] args) {

        ArrayList<Integer> numbers = new ArrayList<Integer>();
        Random r = new Random();

        //Populate array with ten random elements
        for(int i = 0 ; i < 4; i++){
            numbers.add(r.nextInt());
        }

        while(numbers.size() > 1){
            for(int i = 0; i < numbers.size();i++){
                if(i%3 == 0){//Every 3rd element should be true
                    numbers.remove(i);
                }
            }
        }
    }
}

Answer 3

I would simply set the removed to null and then skip nulls in the inner loop.

boolean continue;
do {
   continue = false;
   for( int i = 2; i < list.length; i += 3 ){
      while( list.item(i++) == null &&  i < list.length );
      Sout("Player " + list.item(--i) );
      continue = true;
   }
} while (continue);

I'd choose this over unjustified shuffling of the array.

(The i++ and --i might seem ugly and may be rewritten nicely.)

Answer 4

You could try using an iterator. It's late irl so don't expect too much.

public removeThirdIndex( listOfWords ) {
    Iterator iterator = listOfWords.iterator
    while( iterator.hasNext() ){
        iterator.next();
        iterator.next();
        iterator.next();
        iterator.remove();
    }
}


@Test
public void tester(){
    // JUnit test > main
    List listOfWords = ... // Add a collection data structure with "words"

    while( listOfWords.size() < 3 ) {
        removeThirdIndex( listOfWords ); // collections are mutable ;(
    }

    assertTrue( listOfWords.size() < 3 );
}

Answer 5

Lets back up and look at the problem algorithmically.

• Start at the first item and start counting.
• Go to the next item and increment your count. If there is no next item, go to the beginning.
• If the count is '3', delete that item and reset count. (Or modulo.)
• If there is one item left in the list, stop.

Lets write pseudocode:

function (takes a list)
  remember what index in that list we're at
  remember whether this is the item we want to delete.

  loop until the list is size 1
    increment the item we're looking at.
    increment the delete count we're on

    should we delete?
      if so, delete!
      reset delete count

    are we at the end of the list?
      if so, reset our index

Looking at it this way, it's fairly easy to translate this immediately into code:

public void doIt(List<String> arrayList) {
  int index = 0;
  int count = 0;

  while(arrayList.size() != 1) {
    index = index + 1;
    count = count + 1; //increment count

    String word = arrayList.get(index);//get next item, and do stuff with it

    if (count == 3) {
      //note that the [Java API][1] allows you to remove by index
      arrayList.remove(index - 1);//otherwise you'll get an off-by-one error
      count = 0; //reset count
    }

    if (index = arrayList.size()) {
      index = 0; //reset index
    }
  } 
}

So, you can see the trick is to think step by step what you're doing, and then slowly translate that into code. I think you may have been caught up on fixing your initial attempt: never be afraid to throw code out.

Answer 6

You could use a counter int k that you keep incrementing by three, like k += 3. However, before you use that counter as an index to kick out any array element, check if you already went beyond and if so, subtract the length of this array from your counter k. Also make sure, to break out of your loop once you find out the array has only one element left.

int k = -1;
int sz = list.length;
while (sz > 1)
{
    k += 3;
    if (k >= sz)
    {
        k -= sz;
    }
    list.remove(k);
    sz --;
}

This examples shows that you already know right away how often you will evict an element, i.e. sz - 1 times.

By the way, sz % 3 has only three possible results, 0, 1, 2. With a piece of paper and a cup of coffee you can find out what the surviving element will be depending on that, without running any loop at all!

Answer 7

You could move every third element to a temporary list then use List#removeAll(Collection) to remove the items when you finish each loop...until the master list was empty...