PDA

View Full Version : Java question about removing based on probablity




prostuff1
Nov 6, 2007, 10:58 PM
I am working on an assignment for my class and I am stuck on were to start with the last part.

I need to implement a way to remove based on the percent that a given object appears in the Map(in my case)

Below is a definition of randomUniformChoose(what i am supposed to provide code for)

Returns a char chosen randomly based on the contents of the multiset. This operation does not remove the char from the multiset or change the multiset in any way. In particular, the cardinality of the multiset is the same before and after this method.

Characters should be returned with a random distribution equal to the distribution of characters in the multiset. That is, for a character that appears N times in a multiset of cardinality M, the probability of that character being returned is N / M. For example, a multiset that contains only the character 'a', possibly many times, would always result in an 'a' being generated. On the other hand, a multiset with an equal number of 'a' and 'b' elements would return an 'a' approximately half the time and a 'b' the other half.

Im not really even sure were to start as far as determining what to remove.

Any pointer/nudges in the right direction would be great.

The code i have so far looks like this:
import java.util.HashMap;
import java.util.Set;
import java.util.Map;
import java.util.Collection;

/**
* DenseMultiSetOfChar implements MultiSetOfChar.
*
* @author Kyle Hiltner
*
*/
public class DenseMultiSetOfChar implements MultiSetOfChar
{
private char characterInput=' ';
private static HashMap<Character, Integer> characterMap = new HashMap();

/**
* Create a new DenseMultiSetOfChar with the passed in value.
*
* @param newChar
*/
DenseMultiSetOfChar(char newChar)
{
this.characterInput = newChar;
characterMap = inputIntoMap(this.characterInput);
}

/**
* Input the value from the creation of the DensneMultiSetOfChar into a Map. If the key
* already exists then the value associated with it is updated by one.
*
* @param character a char
* @return characterMap
*/
private HashMap<Character, Integer> inputIntoMap(char character)
{
if(!characterMap.containsKey(character))
{
characterMap.put(character, 1);
}
else
{
int value = characterMap.get(character);
value++;
characterMap.put(character, value);
}

System.out.println(characterMap);
return characterMap;
}

public int getCardinality()
{
int totalElementsInMap=0;
Collection<Integer> integerCollection = characterMap.values();

for(Integer valueFromCollection : integerCollection)
{
totalElementsInMap = totalElementsInMap + valueFromCollection;
}

return totalElementsInMap;
}

public int getElementCount(char target)
{
int numberOfGivenCharacters=0;

if(characterMap.containsKey(target))
{
numberOfGivenCharacters = characterMap.get(target);
}

return numberOfGivenCharacters;
}

public Set<Character> getElementSet()
{
Set<Character> characterSet = characterMap.keySet();

return characterSet;
}

public void add(char item)
{
characterMap = inputIntoMap(item);
}

public boolean remove(char target)
{
boolean answer=false;

if(characterMap.containsKey(target))
{
int value = characterMap.get(target);

if(value == 1)
{
characterMap.remove(target);
}
else
{
value--;
characterMap.put(target, value);
}

answer = true;
}
else
{
answer = false;
}
return answer;
}

public char randomUniformChoose()
{
char randomCharacter=' ';

return randomCharacter;
}
}


Everything that needs to work does work ACCEPT the last randomUniformChoose.



Persifleur
Nov 7, 2007, 06:07 AM
Let's assume you have the following Map:

[ a => 2, b => 1, c => 3, d => 1, e => 3 ]

If it were expanded to appear as an array, it would look like this:

{ a, a, b, c, c, c, d, e, e, e }

Math.random() returns a number between 0 and 1 (including 0, but not including 1) with approximately uniform distribution. If you used (int) (Math.random() * array.length) as your array index, it would randomly select a number between 0 and 9 as the array index to be returned. Because e.g. 'c' appears three times in the array, it is three times more likely to be returned (array[3], array[4] and array[5] will all return 'c').

This idea can be adapted to your Map without resorting to an array.