How to find 1 X 15 array from 3 X 15 array? [closed]
Im trying to create 1 X 15 dimension unique array from 3 X 15 array. I am not able to achieve this .Please help me on this . Thanks in advance.
The 3 X 15 array was
Array[(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3),(1,2,3)]
You have a set of 3 characters (1, 2, 3) and you want every possible word of 15 letters from your alphabet of 3 characters. The solution is recursive:
Let size be your word size, given as parameter
Let alphabet be your character set, given as parameter
If size is 0 then
return collection with empty string
Let result be the collection of possible words, starting empty
Let subset be the solution of the problem for size-1 and alphabet
For every word in subset:
For every character in alphabet:
Let newword be the concatenation of character and word
Add newword to result
return result
In (didactic, unoptimised) javascript:
function words(size, alphabet) {
if(size == 0) return [''];
var result = [];
var subset = words(size-1, alphabet);
for(var i=0; i<subset.length; i++) {
var word = subset[i];
for(var j=0; j<alphabet.length; j++) {
var character = alphabet[j];
var newword = character+word;
result.push(newword);
}
}
return result;
}
words(3,['1','2','3']);
// 111,211,311,121,221,321,131,231,331,112,212,312,122,222,322,132,232,332,113,213,313,123,223,323,133,233,333
note: there are more than 14 millions words of 15 letters with a set of 3 characters. So the computation is quite long.
edit: If your arrays don't always have the same exact 3 characters, then you have to change the first lines of the function. The arrays have to be given as argument, then the function pops the first array which it will use as alphabet and gives the rest to the recursive call:
function words(arrays) {
if(arrays.length == 0) return [''];
var result = [];
var alphabet = arrays.shift();
var subset = words(arrays);
for(var i=0; i<subset.length; i++) {
var word = subset[i];
for(var j=0; j<alphabet.length; j++) {
var character = alphabet[j];
var newword = character+word;
result.push(newword);
}
}
return result;
}
words([['a','b','c'],['d','e','f'],['h','i','j']])
// adh,bdh,cdh,aeh,beh,ceh,afh,bfh,cfh,adi,bdi,cdi,aei,bei,cei,afi,bfi,cfi,adj,bdj,cdj,aej,bej,cej,afj,bfj,cfj
You seem to be mixing javascript with some other language- javascript doesn't have mult-dimensinal arrays, though an array can be composed of arrays (or arrays of arrays)
This is a javascript array of 15 3 member arrays
var a= [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3],
[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3],
[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]];
if you want to collapse it into an array that contains only primitives you can map each element with its String method-
a=a.map(String);
alert(a.join('\n'))
/* returned value:
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
1,2,3
*/
But a unique array in this case would have only one member.
// for IE and older clients you can sub the map method-
if(![].map){
Array.prototype.map= function(fun, scope){
var L= this.length, A= Array(this.length), i= 0, val;
if(typeof fun== 'function'){
while(i< L){
if(i in this){
A[i]= fun.call(scope, this[i], i, this);
}
++i;
}
return A;
}
}
}
As I understand it, you're looking to compute all permutations using the inner arrays of your 3x15 array to specify the set of possibilities at each index for the output array.
Here's a recursive Java solution (I'm not sure what language you're actually using, which is why it's best not to list 4 different languages in your tags):
public static void main(String[] args) throws Exception {
List<int[]> perms = new ArrayList<int[]>();
int[][] a = {{1,2,3},{1,2,3},{1,2,3},{1,2,3},{1,2,3}};
int[] buff = new int[a.length];
recurse(perms, a, buff, 0);
int[][] allPerms = perms.toArray(new int[perms.size()][]);
for ( int[] arr : allPerms ) {
System.out.println(Arrays.toString(arr));
}
}
private static void recurse(List<int[]> perms, int[][] a, int[] buff, int index) {
if ( index == a.length ) {
perms.add(Arrays.copyOf(buff, buff.length));
} else {
for ( int i = 0; i < a[index].length; i++ ) {
buff[index] = a[index][i];
recurse(perms, a, buff, index+1);
}
}
}
The nature of the problem doesn't make recursion all that elegant though.
You have 3^15
(or 14,348,907) possibilities. If the order that the combinations are generated in does not matter, then you can try something like this:
Have a counter count from 0 to 14348906. For each step, the indices into your starting array will be the digits of the base-3 representation of the counter.
For example, if the counter is 0, then this is 000000000000000 in base-3 and you would use indices Array[0][0], Array[1][0], Array[2][0],...,Array[14][0]
.
If the counter is 15463, then this is 000000210012201 in base-3 and you would use indices Array[0][0],...,Array[7][2],Array[8][1],Array[9][0],...,Array[12][2],Array[13][0],Array[14][1]
To convert the decimal number to base 3, repeatedly divide the number by three. Each time you divide, the remainder will be the next digit in the base-3 representation (starting with the least-significant). For example (in pseudo-C):
#include <stdlib.h>
int count, idx, quotient;
div_t result;
int indices[15];
int Array[15][3] = {{1,2,3},{1,2,3}, etc etc}
int* pNewArray;
for (count = 0; count < 14348906; ++count) {
memset(indices, 0, 15*sizeof(int));
result.quot = count;
idx = 0;
while (result.quot > 0) {
result = div(result.quot, 3);
indices[idx++] = result.rem;
}
pNewArray = malloc(15 * sizeof(int));
for (idx = 0; idx < 15; ++idx)
pNewArray[idx] = Array[idx][indices[15-idx]];
DoSomethingWith(pNewArray);
}
Finally - I think I know what you're looking for.
Assuming this:
input = {{"a","b","c"},{"d","e","f"},{"g","h","i"},{"j","k","l"}};
// expected output:
// "adgj", "bdgj", "cdgj", "aegj", "begj", "cegj", ... , "cfil"
// 0000 1000 2000 0100 1100 2100 2222 <-- indexes
The key to your the solution is the numeric sequence in the last comment line. You'll have to generate this sequence and the sequence values as a keys to create your combinations, like:
a_25 => {0,2,2,1} => input[0][0]+input[0][2]+input[0][2]+input[0][1] => "afik"
I chose a different size and content for the input array just to illustrate the idea. The sequence generator will take an array, perform and 'increment' and return the 'incremented' array, like:
increment({0,2,2,1}) -> {0,2,2,2}
increment({0,2,2,2}) -> {1,0,0,0}
Hope it helps to continue with your task.
精彩评论