2.3.3. Changing lists and searching in lists

Learning objectives

Deleting elements
Concatenating, splitting, permuting, and reversing lists
Applying a function to all elements of a list
Searching for elements
The LEDA rule “Illegal access via an item

With the help of the items not only can we modify attributes, that is, change the contents of containers; therewith, we can also delete or insert containers at certain positions, that is, we can change the structure of the list.

As an example we simulate the Josephus problem (see [7]): Flavius Josephus was a famous historian of the first century. According to a legend he was a member of a 41-headed Jewish rebel gang during the Jewish Roman war, who was captured by the Romans in a cave. The rebels, who wanted to prefer suicide to captivity, decided to form a circle. Every third person in the circle should kill itself, one after the other. Josephus, however, wanted to escape this suicide orgy, together with an unknown co-conspirator. Thanks to his mathematical talent, he could reckon fast where he and his friend had to stand in the circle to be left as the last two persons so that they could escape from death. Figure 2.14 shows the death circle for 10 persons.

Figure 2.14. The Josephus problem

The Josephus problem

10 people form a circle. Every third person kills itself, one after the other. Person 0 dies first. The respective number in the elimination order is shown next to the person. Persons 1 and 7 are left.

To simulate this death circle, we read in the number n of persons and store the numbers 0 to n-1 in a list. With an item pos we loop around the circle; we call it the current item. At the beginning, we let this item refer to the first container of the list. We get ourselves an item new_pos, which refers to the next but two container; this container will be deleted in the next iteration. We delete the container belonging to the current item from the list. The item new_pos then becomes the current item. The loop runs until only 2 persons (numbers, elements, containers) are left in the list. We then output the numbers of these persons.

Filename: Josephus.C
#include <LEDA/list.h>
#include <iostream>

using leda::list;
using leda::list_item;
using std::cout;
using std::cin;

int main()
{

  list<int> L;
  int num_persons;

  cout << "Enter number of persons: ";
  cin >> num_persons;

  for(int i = 0; i < num_persons; i++)
    L.append(i);

  list_item pos = L.first();

  while(num_persons > 2) {
    list_item new_pos = pos; // LEDA Rule 3!
    for(int j = 1; j <= 3; j++)
      new_pos = L.cyclic_succ(new_pos);
    cout << "Person " << L.contents(pos) << " must die now.\n";
    L.del_item(pos);
    pos = new_pos;
    num_persons--;
  }
  
  int survivor1 = L.front();
  int survivor2 = L.back();

  cout << "The surviving persons are ";
  cout << survivor1 << " and " << survivor2 << std::endl;
}

A sample program run looks as follows:

Enter number of persons: 10
Person 0 must die now.
Person 3 must die now.
Person 6 must die now.
Person 9 must die now.
Person 4 must die now.
Person 8 must die now.
Person 5 must die now.
Person 2 must die now.
The surviving persons are 1 and 7

The container belonging to a list item it is deleted by a call of

L.del_item(it);

The methods

L.front();
L.back();

do not return an item, but directly the first and last element of the list, that is the contents of the first and last container, respectively.

It is very important in the above program that we delete the current item not until we have read the contents from the respective container by means of contents() and not vice-versa! The reversed order, that is first delete, then read, can lead to serious conflicts and contradicts the LEDA rule “Illegal access via an item”: A container already deleted may not be accessed any more via an item.

Further list modifying operations

LEDA has numerous further operations which lists can be modified with. Two lists can be concatenated and a list can be split into two partial lists in front of or behind a certain element. A list can be reversed and randomly permuted. There is an operation which applies a function defined before to every element of a list. Of course, a list can also be searched for a certain element.

The following program demonstrates these operations.

Filename: ListUpdateOperations.C
#include <LEDA/list.h>
#include <LEDA/string.h>
#include <iostream>

using leda::list;
using leda::list_item;
using leda::string;
using std::cout;

// print a list together with its name and a newline at the end
inline void list_print(const string& name, const list<int>& L) {
  cout << name << ": " << L << "\n";
}

inline void inc(int& x) { x++;}

int main() 
{

  list<int> L, M;

  for(int i=0; i < 10; i++) {
    L.push(i);
    M.append(i);
  }
  list_print("L",L); list_print("M",M);

  L.conc(M, leda::after);
  list_print("L",L); list_print("M",M);

  list_item it = L.search(5);

  list<int> A, B;

  L.split(it, A, B, leda::before);
  list_print("L",L); list_print("A",A); list_print("B",B);

  B.permute();
  list_print("B",B); 

  it = B.first();
  cout << "Item it contains " << B.contents(it) << std::endl;
  B.reverse_items();
  list_print("B",B);
  cout << "Item it still contains " << B.contents(it) << std::endl;

  B.reverse();
  list_print("B",B);
  cout << "Item it now contains " << B.contents(it) << std::endl;

  B.apply(inc);
  list_print("B",B);
}

The output of the program is

L:  9 8 7 6 5 4 3 2 1 0
M:  0 1 2 3 4 5 6 7 8 9
L:  9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
M:
L:
A:  9 8 7 6
B:  5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
B:  2 9 4 0 1 2 5 0 1 8 5 3 6 4 3 7
Item it contains 2
B:  7 3 4 6 3 5 8 1 0 5 2 1 0 4 9 2
Item it still contains 2
B:  2 9 4 0 1 2 5 0 1 8 5 3 6 4 3 7
Item it now contains 7
B:  3 10 5 1 2 3 6 1 2 9 6 4 7 5 4 8

By the operation

L.conc(M);

all containers of the list M are appended at the end of the list L. M is emptied in this process!

it = L.search(x);

searches in a list for an element with value x. The method returns an item referring to the first container which contains the search value; if the search value is not contained in the list, it returns nil.

With the method

L.split(it, A, B , position);

a list can be split at a certain item it into two partial lists A and B. The parameter values leda::before and leda::after specify whether the separation takes place in front of or behind the corresponding container, respectively. That means, it specifies whether this container will belong to the second or to the first partial list, respectively, after the splitting. If the parameter is left out, the list is split in front of this container. The original list is emptied when splitting!

L.permute();

places the containers in a random order. Every order has the same probability.

L.reverse_items();

reverses the linking information in the containers. In doing so, no contents are changed. Attributes of the items remain unmodified. This method modifies the order in which the list is iterated over.

In contrast,

L.reverse();

really swaps the contents of the containers: The first contents are swapped with the last ones etc. The above program clarifies this.

[Warning] Warning

The name reverse_items() is misleading. An item is a reference to a container. Such a reference is not touched at all, it remains totally unmodified. Rather, the result of a call of succ() and pred() is modified. The item returned by the latter methods now refers to its former predecessor and successor container, respectively. The method should therefore better be called reverse_order().

A call of

L.apply(f);

applies a function f() to every element of the list. f() must have return type void; its argument must be passed to it by reference. In the above program apply() is used to increment every number stored in the list.

There are yet some other, less important operations which modify lists; also, the above methods can partly be invoked with other or additional arguments. All this can be looked up on the corresponding manual page.

An application: creating variations

As an application of some of these functions we simulate the German national lottery game “6 from 49”, where a player must give 6 tips for 6 (different) numbers to be drawn out of the numbers 1 to 49. The user may enter 6 numbers. The program then draws 6 numbers randomly from the admissible 49 numbers and calculates how many “straight tips” the user has guessed.

Filename: Choose6from49.C
#include <LEDA/list.h>
#include <iostream>

using leda::list;
using leda::list_item;
using std::cout;

int main() 
{
  std::cout << "Please enter 6 different numbers from 1 to 49:\n";

  list<int> Guess;
  while(Guess.size() != 6) {
    int next_guess;
    std::cin >> next_guess;
    if(Guess.search(next_guess)) {
      cout << next_guess << " is already in your list of numbers. ";
      cout << "Please try again.\n";
    }
    else
      Guess.push(next_guess);
  }


  list<int> Number;

  for(int i = 1; i <= 49; i++) 
    Number.push(i);

  Number.permute();

  list_item it = Number.first();
  for(int i = 1; i <= 6; i++) it = Number.succ(it);
  
  list<int> Choose, Rest;

  Number.split(it, Choose, Rest);

  int num_correct_guesses = 0;
  int my_guess;

  forall(my_guess,Guess)
    if(Choose.search(my_guess))
      num_correct_guesses++;

  std::cout << num_correct_guesses << " of your numbers were chosen.\n";
}

A sample run looks like this:

Please enter 6 different numbers from 1 to 49:
15
19
19
19 is already in your list of numbers. Please try again.
20
4
23
41
1 of your numbers were chosen.

We store the 6 numbers to be entered in a list Guess. For every new number, we search for this number in the list first. If we already find it therein, we output a warning message. We accept only numbers which are not yet contained in the list.[16]

We store the numbers from 1 to 49 in a list Number, permute this list, and split it in front of the 7th container. Thereby, we receive a random drawing of 6 numbers in the list Choose.

In a final step, we search for every number of Guess in Choose and count the number of coincidences.

Exercises

Exercise 13.

In a generalized version of the Josephus problem every m-th person from a set of n persons dies one after the other until only one person is left. Person m-1 dies first.

Write a program which calculates where you should line up in such a circle of death if you want to survive. Caution! It does not suffice to simply replace the validity constraint in the above while loop by L.size() > 1! (Why not?)

Exercise 14.

n boxers exercise in a boxing club. Every boxer shall fight every other boxer once in a sparring tournament. Look at Figure 2.15 for this.

Figure 2.15. Creating pairings

Creating pairings

If the number n of the list elements is even, all elements rotate except for one which is fixed. If n is odd, all elements rotate and there is a fixed resting position.

If n is even, all boxers (apart from boxer 0) must move around in the circle after every round like the links of a chain so that everybody faces boxer 0 once. If n is odd, all boxers must rotate and there is a designated resting position, that is, always one of the boxers suspends.

Work out why this procedure creates every possible pairing exactly once in altogether n-1 or n rounds, respectively, and write a program which efficiently creates the pairings with the help of a list.

In a round tournament in the game of chess, the additional problem arises that every player shall play (approximately) just as often white as black. Here a board is placed in between the pairs of players facing each other in Figure 2.15; the boards are arranged alternately, that is, the left side plays white in the first pairing, black in the second one, white in the third one etc. Player 0 flips his board in every round; the other boards are never flipped. Refine your program so that it additionally outputs which players play with which color.



[16] This method for guaranteeing uniqueness among the elements is efficient here only because we store not more than 6 elements altogether. If we had to store more elements, we should use a different data structure, for example a set.




Imprint-Dataprotection