It seems an interesting problem but pardon me  I could not follow the problem statement ..

 Is it that you want to build the Pascal triangle but it is from (http://mathworld.wolfram.com/PascalsTriangle.html)

a_(nr)=(n!)/(r!(n-r)!)=(n; r), 

 but I think you mean something more interesting.. would you

 care to make a more detailed description with a small example..

 thanks

 Cheers

Can you elaborate a bit more on the problem at hand.  What's its inputs, output, and problem instance.  I am trying to follow but it is a little difficult to pull out exactly what I need to answer this.  What type of algorithm are you after?  Sequential?  Parallel?  I suggest figuring out the sequential algorithm first with in mind the architecture you're working with.

This sounds like something that is already known to be done with loopless algorithms.  If you wanted to parallelize it, you'd probably just need an unrank function.  If you are trying to develop a parallel algorithm, I may have some references to help you out.

Hm - thanks for replying. To get the problem more specific. There are two parts of the code I found out - should work. If i do the code in parallel for two elements like (a+b)^3 there is the possibility to get the line of coefficients by muliplying 1 with (i/j) when i is the exponent-- and j is 1++ then working the line out with the next result so that 1 3 3 1. I also found out, that there are always (exponent + 1) coefficients in one line with two elements - but i stuck with 3 or n elements in the term (trinoms - multinoms ~). Each coefficent gives the amount of how often these elements when using chars instead of numbers can be combinated without giving the same result. The exponent always shows how often a single char is contained in these sets a^2, b^1 whould be a,a,b and can be changed 3 times ... The goal whould be a word generator for crawling a searchengine with all possible charsets in the unicode even unique combinations of them (a hack or a benchmarktest). To avoid loops as mentioned by you before is maby possible - I expected them to be nessesary when calculating several combinations of charsets by defining the exponent and the number of elements.

I think this paper may assist you in getting one method for parallelizing your algorithm.  It sounds like you have an algorithm (maybe) sequentially.  I strongly suggest getting it down for sequential first, then thinking carefully on how to parallelize it.

http://www.site.uottawa.ca/~ivan/Listing-parallel.pdf (Listing combinatorial objects in parallel by Ivan Stojmenovic)

Keep in mind this is not the only way to do it, but if you want to exploit known loopless algorithms for generation of combinatorial objects, these techniques are handy.

Hope this helps!

Please see if the following is useful. This is my understanding of the problem .

1. Consider 2 alphabet case { a,b} then for three letter word we get the following possibilities.

(a+b)^3 = 1. a^3 + 3 a^2b +3 ab^2 + 1.b^3

so we have 1 word with a^3

3 words with a^2b (we are not interested in ranking / unranking I presume)

3 words with ab^2

1 word with b^3

total of 8 words = 2^3

As you have discovered the coefficients 1 3 3 1 tell

how many words can be made with a^3, a^2b ..etc

2 Now with trinomial (a+b+c)^ 3 we can use the same idea .

Set (b+c) =d

then (a+d) ^3 = 1. a^3 + 3 a^2d +3 ad^2 + 1.d^3

so use the algorithm repeatedly for exponent of d>1

finally we get = a^3 +3a^2b+ 3a^2c +3a( b^2+2bc+c^3)+b^3+3b^2c+3bc^2 +c^3

as you visualized we can get the number of permutations of each type.

check total words =1+3+3+3+6+3+3+3+ 1= 27 = 3^3

Cheers

Thx for all the answers!

I attached a trial written in C++ - it's incomplete - could you help me getting on with it?

#include "cpp_vow.cpp"

// buid a server with mains

struct varElemNr {

int elemNr;

int expNr;

int lyr;

} vE;

struct varPool {

int exp_n;

double* koef;

double* elem;

} vP;

struct varIter {

int it_0;

int it_1;

int it_2;

int it_3;

} vI;

struct varStra {

int it_elem;

int it_exp;

} vS;

struct varVow {

int* vow;

}vV ;

struct varRes {

double* res;

} vR;

struct varChr {

int** chr;

} vC;

int main(int argc, char** args) {

vP.koef = NULL;

vP.elem = NULL;

vE.elemNr = 4;

vE.expNr = 4;

// vE.lyr = 1;

vP.exp_n = vE.expNr;

vP.koef = new double[vE.expNr + 1];

vP.elem = new double[vE.elemNr + 1];

for(vI.it_1 = 0; vI.it_1 < vE.expNr + 1; vI.it_1++) {

vP.koef[vI.it_1] = (double) 1.0;

}

for(vI.it_1 = 0; vI.it_1 < vE.elemNr; vI.it_1++) {

vP.elem[vI.it_1] = (double) vI.it_1 + 1;

}

cl_vow_01 obj_001 = cl_vow_01(vE.expNr,vE.elemNr, vP.koef, vP.elem);

// obj_001.meth_genVow(vP.exp_n,(int) pow((double)vE.elemNr,(double) vE.expNr), vP.koef, vP.elem);

obj_001.meth_genVow(vE.expNr,vE.elemNr, vP.koef, vP.elem);

// obj_001.meth_genChr();

delete[] vP.elem;

delete[] vP.koef;

delete[] vV.vow;

delete[] vR.res;

delete[] vC.chr;

return 0;

}

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#ifndef CL_VOW_H

#define CL_VOW_H

class cl_vow_01 {

private:

// Memberdefinition

int exp_;

// Deklaration doubles (Machineword double length to the std of your architecture

double* koef;

double* elem;

int* expn;

// Iteration in

int it_x;

int it_y;

int it_z;

int it_e; // guess as many - > maybe kombinatorically rightness

int it_f;

int it_n;

int it_m;

int it_q;

int it_p;

int elem_;

// double result matrix3d

int** vow;

int* chr;

int*** res;

int*** hre;

public:

cl_vow_01();

cl_vow_01(int exp_n, int elem_n, double* koef, double* elem);

// ructorcut

~cl_vow_01();

// Method public

void meth_genVow(int exp_n, int elem_n, double* koef, double* elem) {

// calculation routine

this->elem_ = elem_n;

this->exp_ = exp_n;

// FILE *file;

// file = fopen("keys.txt", "w");

// fclose (file);

// delete this->res;

for(it_x = 1,it_y = this->exp_; it_x exp_; it_x++, it_y--) {

koef[it_x] *= koef[it_x - 1] * ((double) it_y / (double) it_x);

}

this->expn = new int[this->exp_];

this->chr = new int[this->elem_];

for(it_x = 0; it_x exp_; it_x++) {

this->expn[it_x] = it_x;

}

for(it_x = 0; it_x < this->elem_; it_x++) {

this->chr[it_x] = (char) (65 + it_x);

// fprintf(stdout, "%c", chr[it_x]);

}

for(it_x = 0; it_x exp_; it_x++) {

this->vow = new int*[it_x + 1];

this->res = new int**[it_x + 1];

this->hre = new int**[it_x + 1];

if(it_x != 0) {

for(it_z = 0; it_z < this->elem_; it_z++) {

for(it_y = 0; it_y < this->expn[it_x]; it_y++) {

this->vow[it_x] = new int[it_y + 1];

this->res[it_x] = new int*[it_y + 1];

this->hre[it_x] = new int*[it_y + 1];

this->vow[it_x][it_y] = this->chr[it_z];

for(it_f = 0; it_f < (int) koef[it_x]; it_f++) {

this->res[it_x][it_y] = new int[it_f + 1];

this->hre[it_x][it_y] = new int[it_f + 1];

this->res[it_x][it_y][it_f] = this->vow[it_x][it_y];

fprintf(stdout, "%c", this->res[it_x][it_y][it_f]);

}

}

}

}

}

delete[] this->expn;

delete[] this->chr;

delete[] this->vow;

delete[] this->res;

delete[] this->hre;

}

};

#endif // CL_VOW

#include "cl_vow.h"

// what is this - embarrecing

cl_vow_01::cl_vow_01(int exp_n, int elem_n, double* koef, double* elem) {

}

cl_vow_01::~cl_vow_01() {

}

The Thread does'n get the array - whyever i have no clue - can someone correct this?

Secondly more classes - if it's not possible that the Threads start theirselves

Can you help me?

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

package pacal_multinom_v1;

import java.io.File;

import java.io.IOException;

import java.io.RandomAccessFile;

import java.util.logging.Level;

import java.util.logging.Logger;

/**

*

* @author Georg

*/

public class cl_Thread_v1 {

public static void main(String args[]) {

try {

int exp = 2;

int elem = 2;

int ch_sh = 65;

cl_Pasc_p0 pasc = new cl_Pasc_p0(exp, elem, ch_sh);

pasc.start();

pasc.join();

} catch (InterruptedException ex) {

Logger.getLogger(cl_Thread_v1.class.getName()).log(Level.SEVERE, null, ex);

}

}

}

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

package pacal_multinom_v1;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.RandomAccessFile;

import java.util.logging.Level;

import java.util.logging.Logger;

/**

*

* @author Georg

*/

public class Pacal_multinom_v1 {

/**

* @param args the command line arguments

*/

public static void main(String[] args) {

int exp = 3;

int elem = 2;

int ch_sh = 65;

try {

int it_f = 0;

File[] file = new File[it_f + 1];

RandomAccessFile[] raf = new RandomAccessFile[it_f + 1];

file[it_f] = new File("C:\\Users\\Georg\\Documents\\NetBeansProjects\\pascal_multinom_v1\\src\\pacal_multinom_v1\\cl_Pasc_p" + it_f + ".java");

raf[it_f] = new RandomAccessFile(file[it_f].getAbsolutePath(), "rw");

if (file[it_f].exists()) {

file[it_f].delete();

}

file[it_f].createNewFile();

raf[it_f].writeBytes("package pacal_multinom_v1;");

raf[it_f].writeBytes("public class cl_Pasc_p" + it_f + " extends Thread {");

raf[it_f].writeBytes("private int val_g = 0;private int val_e = 0; private int val_sh = 0;private char[][] arr_s = null ;private char[][] res_ch = new char[2][];");

raf[it_f].writeBytes("public cl_Pasc_p" + it_f + "(int val_e, int val_g, int val_sh) { this.val_g = val_g;this.val_e = val_e; this.val_sh = val_sh;this.arr_s = new char[this.val_e][this.val_g];}");

raf[it_f].writeBytes("@Override ");

raf[it_f].writeBytes("public void run() {");

raf[it_f].writeBytes("for (int it_0 = 0; it_0 < this.val_e; it_0++) { for (int it_1 = 0; it_1 < this.val_g; it_1++) { this.arr_s[it_0][it_1] = (char) (this.val_sh + it_1);}}");

raf[it_f].writeBytes("new Thread(new cl_Pasc_p" + 1 + "(this.res_ch)).start();");

raf[it_f].writeBytes("}");

raf[it_f].writeBytes("public char[][] getArr_s() { return this.arr_s;}");

raf[it_f].writeBytes("}");

} catch (IOException ex) {

System.out.println("Fehler: Couldn't create file" + ex);

}

try {

int it_f = 0;

int it_g = 0;

for (int it_exp = exp, it_up = 0; it_exp >= 2; it_exp--, it_up++) {

for (it_f = 1, it_g = 0; it_f < it_exp - 1; it_f++, it_g++) {

File[] file = new File[it_f + 1];

RandomAccessFile[] raf = new RandomAccessFile[it_f + 1];

file[it_f] = new File("C:\\Users\\Georg\\Documents\\NetBeansProjects\\pascal_multinom_v1\\src\\pacal_multinom_v1\\cl_Pasc_p" + it_f + ".java");

raf[it_f] = new RandomAccessFile(file[it_f].getAbsolutePath(), "rw");

if (file[it_f].exists()) {

file[it_f].delete();

}

file[it_f].createNewFile();

raf[it_f].writeBytes("package pacal_multinom_v1;");

raf[it_f].writeBytes("public class cl_Pasc_p" + it_f + " extends Thread {");

raf[it_f].writeBytes("private int val_g = 0;private int val_e = 0; private int val_sh = 0; private char[][] arr_s = null;private char[][] res_ch = new char[2][];");

if (it_f - 1 == 0) {

raf[it_f].writeBytes("public cl_Pasc_p" + it_f + "(char [][] arr_s) {this.arr_s = arr_s;this.val_g = " + elem + ";this.val_e = 2; this.val_sh = " + ch_sh + "; cl_Pasc_p" + it_g + " cl_pasc" + it_g + " = new cl_Pasc_p" + it_g + " (this.val_g, this.val_e, this.val_sh);}");

} else {

raf[it_f].writeBytes("public cl_Pasc_p" + it_f + "(char [][] arr_s) {this.arr_s = arr_s;this.val_g = " + elem + ";this.val_e = 2; this.val_sh = " + ch_sh + "; cl_Pasc_p" + it_g + " cl_pasc" + it_g + "-1 = new cl_Pasc_p" + it_g + " (this.arr_s);new Thread(new cl_pasc" + (it_g + 1) + "(this.arr_s)).start();}");

}

raf[it_f].writeBytes("@Override ");

raf[it_f].writeBytes("public void run() {");

raf[it_f].writeBytes("int ctr = 0;");

for (int it_e = 0; it_e < 2; it_e++) {

raf[it_f].writeBytes("for(int it_" + it_e + " = 0; it_" + it_e + " < this.val_g; it_" + it_e + "++) {");

}

for (int it_e = 0; it_e < 2; it_e++) {

raf[it_f].writeBytes("this.res_ch[" + it_e + "][ctr] = (char) (this.arr_s[" + it_e + "][it_0] + this.arr_s[" + it_e + "][it_1]);System.out.println(this.arr_s["+ it_e+"][it_1]);ctr++;");

}

for (int it_e = 0; it_e < 2; it_e++) {

raf[it_f].writeBytes("}");

}

raf[it_f].writeBytes("cl_Pasc_p" + it_f + " pasc" + it_f + " = new cl_Pasc_p" + it_f +"(this.arr_s); pasc" + it_f + ".start();");

raf[it_f].writeBytes("}");

raf[it_f].writeBytes("public char[][] getRes_ch() {return this.res_ch;}");

raf[it_f].writeBytes("}");

}

}

} catch (IOException ex) {

System.out.println("Fehler: Couldn't create file" + ex);

}

/*

char[][] ch_arr = null;

for (int it_0 = 0; it_0 < exp - 1; it_0++) {

ch_arr = th_arr[it_0].getArr_ch();

}

*/

/*

for (int it_e = 0; it_e < ch_arr.length; it_e++) {

for (int it_g = 0; it_g < ch_arr[it_e].length; it_g++) {

System.out.print(ch_arr[it_e][it_g]);

}

System.out.println("");

}

*/

}

}

I could solve the problem - here is my way to the test but I can not do a benchmarktest because of the VM limitation - best regards

but it seems to be wrong because the swaping of only one char is to less general - can you give me a hint if such a solution is even possible using no recursion in a common computing language?

now it seems to work correct - thank you for the help

This attempt is correct now

It wasn't another trial gave better results - still i can not write my own Name with 18^18 VM Ware Limit is to little - best regards here is a fast way to do so