How can I make a random set generator with equal possibility to generate uniform sets and non-uniform sets?

Question

So let's say I have a set of items:

['a', 'b', 'c', 'd', 'e']

and I want to generate a random set (order does not matter) from those choices:

['a', 'e', 'd', 'c']

which is child's play, but instead of it being unlikely to generate a uniform result:

['c', 'c', 'c', 'c']

compared to something less uniform like:

['a', 'b', 'e', 'd']

I want to make it equally likely that a uniform set can be generated as it is likely that a non-uniform set can be generated.

Edit:

The result I'm trying to express is not just ['c', 'c', 'c', 'c', 'c', 'c'] or ['d', 'd', 'd', 'd', 'd', 'd'] but also the areas in between those uniformities like ['c', 'c', 'c', 'c', 'c', 'a'] or ['d', 'd', 'd', 'd', 'd', 'b'] or ['c', 'c', 'c', 'c', 'b', 'a']. Making all of those uniform sets and the areas in-between equally likely as non-uniform results is what I find challenging to create. I'm at a loss for where to even begin creating a set generator that does that.

Further clarification:

So if I generate a set of 1000 items, I want it to be equally likely that the set is 90% uniform or 100% uniform or 80% uniform or 20% uniform.

How can/should this be done?

Answer 1

From what you're saying, you want to ignore the order of the elements in your random set, so if your original set was ab then the possible outcomes (ignoring order) would be aa, ab, bb, and you'd like to see each of those appearing with equal probability (of 1/3), no?

A brute-force solution to this would be:

1. generate all outcomes (see Finding All Combinations of JavaScript array values),
2. sort each of the results so the elements appear alphabetically,
3. remove duplicates (see Remove duplicates from an array of objects in javascript)
4. select one of the remaining results at random

So for example, with abc:

all combinations =   [`aaa`, `aab`, `aac`
                      `aba`, `abb`, `abc`
                      `aca`, `acb`, `acc`
                      `baa`, `bab`, `bac`
                      `bba`, `bbb`, `bbc`
                      `bca`, `bcb`, `bcc`
                      `caa`, `cab`, `cac`
                      `cba`, `cbb`, `cbc`
                      `cca`, `ccb`, `ccc`]

sorted combinations = [`aaa`, `aab`, `aac`
                       `aab`, `abb`, `abc`
                       `aac`, `abc`, `acc`
                       `aab`, `abb`, `abc`
                       `abb`, `bbb`, `bbc`
                       `abc`, `bbc`, `bcc`
                       `aac`, `abc`, `acc`
                       `abc`, `bbc`, `bcc`
                       `acc`, `bcc`, `ccc`]

remove duplicates  = [`aaa`, `aab`, `aac`,
                      `abb`, `abc`, `acc`,
                      `bbb`, `bbc`, `bcc`,
                      `ccc`]

then choose from these with equal probability of 1/10

---

EDIT The final output above gives a clue to a non-brute-force solution: for each item the letters that follow each letter are of equal or 'higher' value (alphabetically speaking). So 'b' will never be followed by 'a', and 'c' will never be followed by 'a' or 'b' and so on.

So we can recursively generate all the combinations like this (sorry it's in python, you'll have to translate to javascript):

r=['a','b','c','d']

def get_combos(bound, n):
  global r
  if n == 1:
    return r[bound:]
  result=[]
  for i in range(bound,len(r)):
    for combo in get_combos(i, n-1):
      result.append(r[i]+combo)
  return result

x = get_combos(0,len(r))
print(x) # ['aaaa', 'aaab', 'aaac', 'aaad', 'aabb', 'aabc', 'aabd', 'aacc', 'aacd', 'aadd', 'abbb', 'abbc', 'abbd', 'abcc', 'abcd', 'abdd', 'accc', 'accd', 'acdd', 'addd', 'bbbb', 'bbbc', 'bbbd', 'bbcc', 'bbcd', 'bbdd', 'bccc', 'bccd', 'bcdd', 'bddd', 'cccc', 'cccd', 'ccdd', 'cddd', 'dddd']

print(len(x)) # 35

Answer 2

This can in fact be done. Just get a random number, and if it is over 0.5 then generate a random set, otherwise generate an extreme set from a random index. See the following code:

function generateRandomOrExtremeSet(a) {
   var n = Math.random();
   var set = [];
   if (n > 0.5)
      for (var i = 0; i < a.length; ++i)
         set[i] = a[Math.round(Math.random()*(a.length-1))];
   else {
      var index  = Math.round(Math.random() * (a.length-1));
      for (var i = 0; i < a.length; ++i) {
         if (Math.random() > 0.8) // change to adjust extremeness
            set[i] = a[Math.round(Math.random()*(a.length-1))];
         else
            set[i] = a[index];
      }
   }
   return set;  
}

Answer 3

Here's a simple snippet that gets it done, using the strategy of first deciding whether to generate an extreme or non-extreme set.

const choices = ['a', 'b', 'c', 'd', 'e']

const repeatN = (times, x) => {
  const ret = [];
  while (times--) {
    ret.push(x);
  }
  return ret;
}

const chooseN = (n, choices) => {
  let list = choices.slice();
  let ret = [];
  while (n-- && list.length) {
    let i = Math.floor(Math.random() * list.length);
    ret.push(list[i]);
  }
  return ret;
};

const set = Math.random() > 0.5 ? 
  chooseN(5, choices) :
  repeatN(5, chooseN(1, choices)[0]);

console.log(set);

Answer 4

Your original question seems to be stated incorrectly, which is why you are getting so many incorrect responses. In fact, the simple approach will give you the result that you want. You should do this by choosing a random value from your original set, like this:

function randomSet(set, size) {
  let result = []
  for (let i = 0; i < size; i++) {
    // get a random index from the original set
    let index = Math.floor(Math.random() * set.length)
    result.push(set[index])
  }
  return result
}

console.log(randomSet(['a', 'b', 'c'], 3))

// These are all equally likely:
// ['a','a','a']
// ['a','b','b']
// ['a','b','c']
// ['c','b','a']
// ['a','b','a']
// ['a','a','b']
// ['b','a','a']
// ['b','a','b']
// ['b','b','b']
// etc.

Alternatively, it's possible that you are misunderstanding the definition of a set. Many of your examples like ['c', 'c', 'c', 'c', 'b', 'a'] are not sets, because they contain repeat characters. Proper sets cannot contain repeat characters and the order of their contents does not matter. If you want to generate a random set from your initial set (in other words, generate a subset), you can do that by picking a size less than or equal to your initial set size, and filling a new set of that size with random elements from the initial set:

function randomSet(set) {
  let result = []
  let size = Math.floor(Math.random() * set.length)
  while(result.length !== size) {
    // get a random index from the original set
    let index = Math.floor(Math.random() * set.length)
    // in this case, we construct the new set simply by removing items from the original set
    result.splice(index, 1)
  }
  return result
}

console.log(randomSet(['a', 'b', 'c']))

// These are all equally likely:
// ['a','b','c']
// ['a','b']
// ['b','c']
// ['a','c']
// ['a']
// ['b']
// ['c']
// no other sets are possible