Pascal's triangle problem

Gradius · Aug 02, 2013#12013-08-02T03:00+00:00

I have a problem with chars combination, using Pascal's triangle principle.

The universe is "a b c d e f g h i j k l m n o p q r s t" (20 chars in total), limited to 10 chars per line.

Using Excel I got:

Code: Select all

=COMBIN(20;10)

Total: 184756

See COMBIN for a description of this Excel function.

So I need a script where it calcs this (real example below):

Code: Select all

a,b,c,d,e,f,g,h,i,j
a,b,c,d,e,f,g,h,i,k
a,b,c,d,e,f,g,h,i,l
a,b,c,d,e,f,g,h,i,m
a,b,c,d,e,f,g,h,i,n
a,b,c,d,e,f,g,h,i,o
a,b,c,d,e,f,g,h,i,p
a,b,c,d,e,f,g,h,i,q
a,b,c,d,e,f,g,h,i,r
a,b,c,d,e,f,g,h,i,s
a,b,c,d,e,f,g,h,i,t
a,b,c,d,e,f,g,h,j,k
a,b,c,d,e,f,g,h,j,l
a,b,c,d,e,f,g,h,j,m
a,b,c,d,e,f,g,h,j,n
a,b,c,d,e,f,g,h,j,o
a,b,c,d,e,f,g,h,j,p
a,b,c,d,e,f,g,h,j,q
a,b,c,d,e,f,g,h,j,r
a,b,c,d,e,f,g,h,j,s
a,b,c,d,e,f,g,h,j,t
a,b,c,d,e,f,g,h,k,l
a,b,c,d,e,f,g,h,k,m
a,b,c,d,e,f,g,h,k,n
a,b,c,d,e,f,g,h,k,o
a,b,c,d,e,f,g,h,k,p
a,b,c,d,e,f,g,h,k,q
a,b,c,d,e,f,g,h,k,r
a,b,c,d,e,f,g,h,k,s
a,b,c,d,e,f,g,h,k,t
a,b,c,d,e,f,g,h,k,m

Last one should be: k,l,m,n,o,p,q,r,s,t

I don't need the "," (commas) is just to make it easier to read for humans (can easily be added manually with UltraEdit after).

I looked for examples, but all them just uses numbers, and this is a bit different as you can see.

Any help would be appreciate.

Mofi · Aug 02, 2013#22013-08-02T17:02+00:00

There is Combinations and Permutations in JavaScript where Math.max(k,n-k) should (must) be replaced by k=(k < n-k) ? n-k : k; as in first comment suggested.

As you wrote, the combination functions work with integer values and not with characters or strings. But each character has a code value (Unicode value = integer value). So why not using charCodeAt() method of JavaScript String object you can get the integer value of every character of a string (97 to 116 for your universe) without or with subtraction by 97 or 96? To output the result as string you may need finally the fromCharCode() method without or with adding 97 or 96 first to every number.

Gradius · Aug 02, 2013#32013-08-02T20:07+00:00

Hi Mofi,

I'm aware of ASCII table, that would be an easier approach, however and I'm not good with javascript or java.

A good ascii table can be found here:
http://www.asciitable.com

So 97 until 116 is correct.

If I got it right, it should be something like this?

Code: Select all

function productRange(a,b) {
  var product=a,i=a;
 
  while (i++<b) {
    product*=i;
  }
  return product;
}
 
function combinations(n,k) {
  if (n==k) {
    return 1;
  } else {
    k=(k < n-k) ? n-k : k;
    return productRange(k+1,n)/productRange(1,n-k);
  }
}

I also know that:

Code: Select all

var n = String.fromCharCode(97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116);

Would give me: abcdefghijklmnopqrst

But I'm stuck there.

Mofi · Aug 04, 2013#42013-08-04T16:20+00:00

I needed a while to understand that you do not want just the total number of combinations, but also each combination written into a file. For this purpose the functions above could not be used as they are just for calculating the total number of combinations. So I searched the web and quickly found the combination generator.

I looked on source of this webpage, more precisely on the JavaScript code, and adapted the two functions for an UltraEdit script. But my first attempts with my code resulted in script errors during script execution or even crashes of UltraEdit because of out of memory conditions. To avoid those heavy memory usage during script execution I finally got following script code to work:

Code: Select all

// http://mysite.verizon.net/res148h4j/javascript/script_combinations.html

function calc_combinations(nN,nK)
{
   var c = 1;
   if (nK > nN) return 0;
   var d = nN - nK;

   while (nN > nK)
   {
      c = c * nN;
      --nN;
   }

   while (d)
   {
      c = c / d;
      --d;
   }

   return c;
}

function list_combinations(nN,nK)
{
   // Create an array of elements.
   var a = new Array();                     // initialize
   for (i = 0; i < nK; i++)
      a[i] = i + 1;                         // 1 - 2 - 3 - 4 - ...

   var nLineCount = 0;
   while (true)
   {
      var sLine = "";
      for (i = 0; i < (nK-1); i++)
      {
         sLine += String.fromCharCode(a[i] + 96) + ',';
      }
      sLine += String.fromCharCode(a[i] + 96) + "\r\n"
      UltraEdit.clipboardContent += sLine;
      if(++nLineCount == 500)
      {
         UltraEdit.activeDocument.paste();
         UltraEdit.clearClipboard();
         nLineCount = 0;
      }

      // generate next combination in lexicographical order
      i = nK - 1;                           // start at last item
      while (a[i] == (nN - nK + i + 1))     // find next item to increment
         --i;

      if (i < 0) break;                     // all done
      ++a[i];                               // increment

      // do next
      for (j = i + 1; j < nK; j++)
         a[j] = a[i] + j - i;
   }
   UltraEdit.activeDocument.paste();
}

var nTotal = calc_combinations(20,10);
if (nTotal > 0)
{
   UltraEdit.newFile();
   UltraEdit.activeDocument.unicodeToASCII();
   UltraEdit.activeDocument.unixMacToDos();
   UltraEdit.selectClipboard(9);
   UltraEdit.clearClipboard();
   list_combinations(20,10);
   UltraEdit.activeDocument.top();
   UltraEdit.clearClipboard();
   UltraEdit.selectClipboard(0);
}

But I was not happy with this working solution. I could see that the output file is smaller than 4 MB and therefore thought: "It must be possible to build the entire output string in memory and paste it into a new file at once making the script much faster. I just need to avoid all those memory allocations and string concatenations during script execution."

As I don't know how to create a string object with a fixed size and modify each character within the string in case this is possible at all in JavaScript, I finally found a solution which is very quick as the entire string is created in memory and written (pasted) at once into a new file.

Code: Select all

// The two functions calc_combinations and list_combinations are from
// http://mysite.verizon.net/res148h4j/javascript/script_combinations.html
// with some small modifications to get the wanted output in UltraEdit.

function calc_combinations(nN,nK)
{
   var c = 1;
   if (nK > nN) return 0;
   var d = nN - nK;

   while (nN > nK)
   {
      c = c * nN;
      --nN;
   }

   while (d)      // The division below can result in a float number like
   {              // c = 377.99999999999994 for nN = 28 and nK = 2. This
      a = c / d; // must be avoided by checking remainder of the division.
      c = ((c % d) == 0) ? a : Math.ceil(a);
      --d;
   }

   return c;
}

function list_combinations(nN,nK)
{
   var nCombinations = calc_combinations(nN,nK);
   if (nCombinations < 1) return;

   // Create an array of elements for one combination.
   var a = new Array(nK);                 // initialize
   for (i = 0; i < nK; i++)
   {
      a[i] = i + 1;                       // 1 - 2 - 3 - 4 - ...
   }

   // Create an array of characters (= single character strings) for all
   // combinations. For every element of a combination 2 characters are
   // needed - the letter and a comma respectively carriage return. And
   // one line-feed is needed additionally for every combination.
   var nSize = nCombinations * (nK * 2) + nCombinations;
   var asChars = new Array(nSize);
   var nIndex = 0;

   while (true)
   {
      for (i = 0; i < (nK-1); i++)
      {
         // Addition by 96 converts the numbers 1 to 20 to the character
         // codes 97 to 116 of the small letters 'a' to 't'.
         asChars[nIndex++] = String.fromCharCode(a[i] + 96);
         asChars[nIndex++] = ',';
      }
      asChars[nIndex++] = String.fromCharCode(a[i] + 96);
      asChars[nIndex++] = '\r';
      asChars[nIndex++] = '\n';

      // generate next combination in lexicographical order
      i = nK - 1;                         // start at last item
      while (a[i] == (nN - nK + i + 1))   // find next item to increment
      {
         --i;
      }

      if (i < 0) break;                   // all done
      ++a[i];                             // increment

      // do next
      for (j = i + 1; j < nK; j++)
      {
         a[j] = a[i] + j - i;
      }
   }

   // Create a new file and make sure it is an ASCII file with DOS line
   // terminators in case of something different configured for new files.
   UltraEdit.newFile();
   UltraEdit.activeDocument.unicodeToASCII();
   UltraEdit.activeDocument.unixMacToDos();
   // Writing a large string to a file is very slow in UE v19.10.0.1012.
   // Therefore the complete string is built in user clipboard 9
   // and pasted into the file to speed up generating the output.
   UltraEdit.selectClipboard(9);
   UltraEdit.clipboardContent = asChars.join("");
   UltraEdit.activeDocument.paste();
   UltraEdit.clearClipboard();
   UltraEdit.selectClipboard(0);
   UltraEdit.activeDocument.top();
}

list_combinations(20,10);

As you can see with looking on the code above, you only have to modify the last line if you want another list using charaters as long as you do not specify values for nN and nK resulting in an out of memory condition due to a too large total number of possible combinations.

To output the combinations without the commas, calculate the size of the array with

var nSize = nCombinations * nK + nCombinations * 2;

and comment or remove the line with asChars[nIndex++] = ',';

Gradius · Aug 05, 2013#52013-08-05T05:10+00:00

Mofi,

Thank you very much!

You're the Wizard!