Implement a Multiset in JavaScript
This post will discuss how to implement a Multiset in JavaScript.
A multiset is a collection that allows multiple occurrences of the same element, unlike a set that only allows unique elements. A multiset keeps track of how many times each element appears. A multiset can be useful for counting, statistics, or other applications that require frequency information. JavaScript does not have a native support for multisets, but there are several ways to implement them using existing data structures or libraries. Here are some of the ways to implement a multiset in JavaScript:
1. Using a Map object
A Map object is a collection of key-value pairs, where each key can only occur once. We can use a Map object to store the elements as keys and their counts as values, and then implement the multiset functions using the Map functions. Here’s an example of how we can achieve this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
// Define a class for a multiset using a Map object class Multiset { // Create a Map object as the backing store constructor() { this._backing = new Map(); } // Define a function to add an element to the multiset add(element) { // If the element already exists in the map, increment its count if (this._backing.has(element)) { this._backing.set(element, this._backing.get(element) + 1); } else { // Otherwise, set its count to 1 this._backing.set(element, 1); } } // Define a function to remove an element from the multiset delete(element) { // If the element exists in the map and has a positive count, decrement its count if (this._backing.has(element) && this._backing.get(element) > 0) { this._backing.set(element, this._backing.get(element) - 1); } else { // Otherwise, do nothing return; } } // Define a function to get the count of an element in the multiset getCount(element) { // If the element exists in the map and has a positive count, return its count if (this._backing.has(element) && this._backing.get(element) > 0) { return this._backing.get(element); } else { // Otherwise, return 0 return 0; } } // Define a function to get the size of the multiset size() { // Initialize a variable to store the total count let total = 0; // Iterate over the values of the map and add them to the total for (let count of this._backing.values()) { total += count; } // Return the total count return total; } } // Test the class on some examples let ms = new Multiset(); ms.add(1); ms.add(2); ms.add(1); ms.add(3); console.log(ms.getCount(1)); // 2 console.log(ms.size()); // 4 console.log(ms); // Multiset { _backing: Map { 1 => 2, 2 => 1, 3 => 1 } } ms.delete(1); console.log(ms.getCount(1)); // 1 console.log(ms.size()); // 3 console.log(ms); // Multiset { _backing: Map { 1 => 1, 2 => 1, 3 => 1 } } |
2. Using an array
An array is a collection of ordered and indexed elements. We can use an array to store the elements of the multiset without any restriction on their uniqueness or order. We can then implement the multiset functions using the array functions or loops. Here’s an example of how we can achieve this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
// Define a class for a multiset using an array class Multiset { // Create an array as the backing store constructor() { this._backing = []; } // Define a function to add an element to the multiset add(element) { // Push the element to the end of the array this._backing.push(element); } // Define a function to remove an element from the multiset delete(element) { // Find the index of the first occurrence of the element in the array let index = this._backing.indexOf(element); // If the index is not -1, splice it out of the array if (index !== -1) { this._backing.splice(index, 1); } else { // Otherwise, do nothing return; } } // Define a function to get the count of an element in the multiset getCount(element) { // Initialize a variable to store the count let count = 0; // Iterate over the elements of the array for (let item of this._backing) { // If the item is equal to the element, increment the count if (item === element) { count++; } } // Return the count return count; } // Define a function to get the size of the multiset size() { // Return the length of the array return this._backing.length; } } // Test the class on some examples let ms = new Multiset(); ms.add(1); ms.add(2); ms.add(1); ms.add(3); console.log(ms.getCount(1)); // 2 console.log(ms.size()); // 4 console.log(ms); // Multiset { _backing: [ 1, 2, 1, 3 ] } ms.delete(1); console.log(ms.getCount(1)); // 1 console.log(ms.size()); // 3 console.log(ms); // Multiset { _backing: [ 2, 1, 3 ] } |
3. Using a library
A third way to implement a multiset in JavaScript is to use a library that provides this functionality, such as mnemonist. This library offer various functions and options for creating and manipulating multisets, such as adding, deleting, counting, iterating, etc. For instance:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// import MultiSet from mnemonist let MultiSet = require("mnemonist/multi-set"); // create an empty MultiSet let multiset = new MultiSet(); multiset.add("apple"); // add one apple multiset.add("banana", 2); // add two bananas multiset.add("apple"); // add another apple console.log(multiset); // MultiSet { "apple": 2, "banana": 2 } multiset.delete("banana"); // remove bananas from the MultiSet console.log(multiset); // MultiSet { "apple": 2 } console.log(multiset.has("apple")); // true |
That’s all about implementing a Multiset in JavaScript.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)