CODEWITHSUNDEEP
javascriptstring
Zach Gates
Zach Gates

Reputation: 4155

Randomly space characters throughout string?

To shuffle a string, I could use something like this

String.prototype.shuffle = function () {
    var arr = this.split("");
    var len = arr.length;
    for (var n = len - 1; n > 0; n--) {
        m = Math.floor(Math.random() * (n + 1));
        tmp = arr[n];
        arr[n] = arr[m];
        arr[m] = tmp;
    }
    return arr.join("");
}

But how could I randomly space it with n characters, while preserving the string order?

For example:

"test"   =>   "t-es--t"
"test"   =>   "-t-e-st"
"test"   =>   "te--st-"

I've thought about creating a list from the string, generating a random number to represent an index, and then shifting the list to the left, but is there a better way to do this?

Upvotes: 2

Views: 2225

Answers (6)

Yotam Omer
Yotam Omer

Reputation: 15376

Working jsFiddle

Even though I loved @Barmar 's idea.. You can do it by simply looping and randomizing positions to insert the spaces.. 

String.prototype.insertSpaces = function (n, char) {
    var str = this;
    for(var i = 0; i < n; i++){
        var randPos = Math.floor(Math.random() * (str.length + 1)); // get random index to insert
        str = str.substring(0, randPos) + char + str.substring(randPos, str.legnth); // insert the repeated sting
    }  
    return str;        
}

Upvotes: 2

Rick Hitchcock
Rick Hitchcock

Reputation: 35670

This will insert n characters char randomly into the string. If char is missing, it defaults to a space:

String.prototype.shuffle = function(n, char) {
  var arr = this.split(''),
      char= char || ' ';

  while(n--) {
    arr.splice(Math.floor(Math.random() * (arr.length+1)), 0, char);
  }

  return arr.join('');
} //shuffle

This Fiddle shows the relative random distribution using the method.

Upvotes: 3

Luis R
Luis R

Reputation: 1

String.prototype.addspace = function () {
var arr = this.split("");
var len = arr.length;
maxSp = 4;
for(var i = 0; i <= len; i++){
    m = Math.floor(Math.random() * (maxSp + 1));
    for(var j = 0; j < m ; j++){
        arr.splice(i,0," ");
    }
    len += m;
    i +=m;
}
return arr.join("");

}
alert("Juanito".addspace().shuffle());

Upvotes: 0

Jason S
Jason S

Reputation: 189836

If you want a truly unbiased solution that produces all possibilities equally likely, and have access to a perfect random number generator (which is a whole other topic), there's a fairly easy solution. Let's define some terms:

  • m = number of characters in the string
  • k = number of spaces you want to insert (you called this n)

Consider one solution to this problem with m=7 and k=3:

0123456789
cab ba g e

What the problem essentially amounts to is choosing k different numbers from among a set of m+k numbers. There are (m+k)!/(m!*k!) possibilities. This is the concept of combinations and is similar to the stars-and-bars problem in the Wikipedia page. (To get an unbiased generator you would need a random number generator with the number of state values much higher than this number of possibilities. But I said RNGs are a whole other topic.)

Here's an example in Python showing all possibilities:

import itertools

def show_all(s, k):
    # show all combinations of k spaces inserted into string s
    m = len(s)
    for sample in itertools.combinations(range(m+k),k):
        jprev = 0
        out = ''
        for ispace, i in enumerate(sample):
            j = i-ispace    # adjust index by number of spaces used
            out += s[jprev:j] + ' '
            jprev = j
        out += s[jprev:]
        yield sample, out

for sample, out in show_all('shoe',2):
    print sample,':'+out+':'

output:

(0, 1) :  shoe:
(0, 2) : s hoe:
(0, 3) : sh oe:
(0, 4) : sho e:
(0, 5) : shoe :
(1, 2) :s  hoe:
(1, 3) :s h oe:
(1, 4) :s ho e:
(1, 5) :s hoe :
(2, 3) :sh  oe:
(2, 4) :sh o e:
(2, 5) :sh oe :
(3, 4) :sho  e:
(3, 5) :sho e :
(4, 5) :shoe  :

Now the problem becomes one of generating a random combination. In Python this is part of the itertools recipes:

def random_combination_with_replacement(iterable, r):
    "Random selection from itertools.combinations_with_replacement(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.randrange(n) for i in xrange(r))
    return tuple(pool[i] for i in indices))

In Javascript we have to implement this ourselves, which we can do using Robert Floyd's algorithm for sampling without replacement:

pseudocode:

initialize set S to empty
for J := N-M + 1 to N do
  T := RandInt(1, J)
  if T is not in S then
    insert T in S
  else
    insert J in S

Javascript:

function random_comb(r, n, m)
{
   /* Generate a combination of m distinct random integers between 0 and n-1
      using Floyd's algorithm

      r: random generation function
         such that r(k) generates an integer in the range [0, k-1]
    */
   var S = {};
   var out = [];
   for (var i = 0; i < m; ++i)
   {
      var j = i+(n-m);
      var t = r(j+1);
      var item = (t in S) ? j : t;
      S[item] = 1;
      out.push(item);
   }
   return out.sort();
}

Now let's put it all together, ignoring the fact that Math.random() is inadequate:

var r = function(n) { return Math.floor(Math.random()*n); }
function random_comb(r, n, m)
{
  /* Generate a combination of m distinct random integers between 0 and n-1
          using Floyd's algorithm

          r: random generation function
             such that r(k) generates an integer in the range [0, k-1]
        */
  var S = {};
  var out = [];
  for (var i = 0; i < m; ++i)
  {
    var j = i+(n-m);
    var t = r(j+1);
    var item = (t in S) ? j : t;
    S[item] = 1;
    out.push(item);
  }
  return out.sort();
}
function random_insert(r, s, k, c)
{
  /* randomly insert k instances of character c into string s */
  var m = s.length;
  var S = random_comb(r, m+k, k);
  var jprev = 0;
  var out = '';
  for (var ispace = 0; ispace < k; ++ispace)
  {
    var i = S[ispace];
    var j = i - ispace;   // adjust index by # of spaces
    out += s.slice(jprev,j) + c;
    jprev = j;
  }
  out += s.slice(jprev);
  return out;
}

var word = 'shoe';
var results = [];
for (var i = 0; i < 10; ++i)
{
  results.push(random_insert(r,word, 2, '-'));
}
var tally = {};
for (var i = 0; i < 100000; ++i)
{
  var s = random_insert(r,word,2,'-');
  tally[s] = (s in tally) ? (tally[s] + 1) : 1;
}
for (var s in tally)
{
  results.push(s+": "+tally[s]);
}
for (var i = 0; i < results.length; ++i)
{
  $("#results").append(results[i]+'<br>');
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
    <div id="results"></div>

Upvotes: 2

jparaya
jparaya

Reputation: 1339

You can use the slice function insert the new character:

var x = "this is phrase";
var y = " a";
[x.slice(0,7), y, x.slice(7)].join('');
Result: this is a phrase

Something like this:

String.prototype.shuffle2 = function() {
  'use strict';
  var numberOfSpaces = Math.floor(Math.random() * (this.length - 1));
  var word = this;
  for (var i = 0; i < numberOfSpaces; i++) {
    var index = Math.floor(Math.random() * (this.length - 1));
    word = [word.slice(0,index), '-', word.slice(index)].join('');
  }
  return word;
};

Greetings!

Upvotes: 0

Scimonster
Scimonster

Reputation: 33409

function addRandomSpaces(str,n,char){
    for (var newstr="", i=0; i<str.length;){
        if (n && Math.random()<0.5) {
            newstr += char;
            n--;
        } else {
            newstr += str[i++];
        }
    }
    while(n--){
        newstr += char;
    }
    return newstr;
}

Here's a function that will loop through a given string str, adding n instances of char at random places. If when it finishes, n items haven't been added, it adds finishes them at the end.

Upvotes: 0

Related Questions