View Full Version : Permutations/combinations
krycek
11-17-2002, 11:26 PM
I need to create a function that loops through different permutations/combinations (which one? not sure!) until it finds the right one. Like, dare I say it, a password brute forcer, however this is NOT intended to be used for anything like that.
I need to simply loop through the combinations, for instance how to do that with "hello"...?
Thanks!
::] krycek [::
chrismiceli
11-18-2002, 01:44 AM
not sure how you would know when the combination is correct, but you could loop through stuff until it matches something else like this
for (var i = 0; result != true; ++i) { //assuming result would be true when code is correct
if (result == true) {
alert("correct, combo is" + i)
}
}
is that something close??
krycek
11-18-2002, 02:12 AM
...ummm, thanks chris but I am asking HOW to do the actual permutations :)
What I am after is the best way in which to cycle through each and every different combination, e.g.
abc
acb
bac
bca
cab
cba
etc.
Along the same lines, if I have "hello" and want to change it into "llhoe" for example, how could I measure the permutations in such a way that I could reverse the operation?
::] krycek [::
chrismiceli
11-18-2002, 03:10 AM
ok, like this
<html>
<head>
<script type="text/javascript">
hello0 = "abc";
hello = hello0.length * hello0.length;
hello0.split();
hello2 = hello0.length - 1;
function combo() {
for (var i = 1;i <= hello; ++i) {
hello1 = hello0[Math.round(Math.random() * hello2)] + hello0[Math.round(Math.random() * hello2)] + hello0[Math.round(Math.random() * hello2)];
alert(hello1);
}
}
</script>
</head>
<body>
<form name="myForm">
<input type="button" onClick="combo()" value="combo">
</form>
</body>
</html>
you might have to alter it for your porpuses.
krycek
11-18-2002, 01:30 PM
hmmm... hello0 * hello0...
the amount of combinations can be given by n * n(n-1) * n(n-2)... etc.
e.g. 5*4*3*2*1 where 5 is the length of the string
As I am looking for looping through combinations of a string of length n, the routine has to take that into account.
Also, the most important thing is, is it possible to find out the "difference" between combinations, using a function/equation rather than actually physically looping through each one until the matching one is found?
e.g.
If I have a password that can ONLY be made up of these letters:
aabbccddee
and I choose
cdaebcdaeb
then is it somehow possible to express one as a function of the other?
Meaning, that by performing the function on aabbccddee you get the password, and in reverse on the password, you get aabbccddee?
Because obviously, each extra character will increase the possible combinations by a power of n, which will take some time to process.
::] krycek [::
x_goose_x
11-18-2002, 05:07 PM
I think I've done what you want, but you must realize javascript isn't really designed to handle such a load. This script is unstable and takes a while to process. But what the heck. Here it is.
<html>
<head>
<script type="text/javascript">
char = new Array();
function run(source,target) {
tmp = "";
source2 = source;
target2 = target;
pophtml = "Calculating...<scr"+"ipt>\n";
for (x=0; x<source.length; x++) {
char[x] = source.charAt(x);
}
for (x=0; x<source.length; x++) {
pophtml += "for (t"+x+"=0; t"+x+"<opener.source2.length; t"+x+"++) {\n";
if (x!=source.length-1) {
pophtml += "opener.tmp += opener.source2.charAt(t"+x+");\n";
}else{
pophtml += "opener.tmp += opener.source2.charAt(t"+x+")+',';\n";
}
}
for (x=0; x<source.length; x++) {
pophtml += "};\n"
}
pophtml += "opener.tmp2 = opener.tmp.split(',');\n"+
"for (x=0; x<opener.tmp2.length; x++) {\n"+
"if (opener.source2.length==opener.tmp2[x].length) {\n"+
"opener.tmp2[x] = opener.tmp2[x];\n"+
"}else{\n"+
"opener.tmp2[x] = opener.tmp2[(x-1)].substring(0,opener.tmp2[x-1].length-opener.tmp2[x].length)+opener.tmp2[x];\n"+
"};\n"+
"};\n"+
"opener.tmp2.pop();\n"+
"opener.target2.value=opener.tmp2;\n"+
"self.close();";
pophtml += "</scr"+"ipt>";
pop = window.open('','','top=0,left=0,width=10,height=10');
pop.blur();
pop.document.write(pophtml);
}
</script>
</head>
<body>
<form>
<input type="text" name="first" value="abc" style="width: 445px;">
<input type="button" onclick="run(this.form.first.value,this.form.txt)" value="GO" style="width: 50px;">
<br>
<textarea name="txt" style="width: 600px; height: 300px;" rows="1" cols="20"></textarea>
</form>
<br><br>
This is a high demand function. It may seem as if it is frozen for a bit, just give it time to complete.
<br><br>
1 char = <1sec<br>
2 char = 1sec<br>
3 char = 2sec<br>
4 char = 4sec<br>
5 char = 55sec<br>
</body>
</html>
My time trial:
1 char = <1sec
2 char = 1sec
3 char = 2sec
4 char = 4sec
5 char = 55sec
Man I need a job.
krycek
11-18-2002, 05:56 PM
I tried it out... interesting, and neraly there.
The script you wrote calculates permutations, i.e. if the letters are a, b, c, it will do aaa, aab, aac, aba, abb, abc, etc.
However, I want *combinations* of the orginal string...
abc can therefore only be, abc, acb, bac, bca, cab, cba
with your script, the calculations required are v^n, where v is the variety in characters, and n is the length of the string. I am trying to do calculations n*n(n-1)*n(n-2)*n(n-3) etc. (I am not sure if that is the right notation).
so, with 5 different characters in a string 5 long, your script would calculate 5^5 = 3125, whereas I only need 5*4*3*2*1 = 120.
Actually, thinking about it, your method may even be working out n^n, if it does not take into account the range of characters...
hopefully you see what I am trying to do :)
the irony is, I could do your script myself, although I probably would not have done it so nicely... you obviously spent some time on it, it is a pity that it is not quite what I am after...
I have fiddled around a bit but I still can't get it to "shuffle" the characters properly, oh well...
However, the most important thing is, is it possible to express the result as a function of the starting string? i.e. without having to do all the calculations and comparisions...
for instance, if I take the char codes of each character and combine them in a string, and divide the string of the original by the string of the result, I get a number which, when multiplied by the result, gives the original. However, the trouble is that most of the time this number will be at least as long as the original number...
So instead, building on that technique, I need to somehow work out how to express one string as a function of the other. I do not even know if that is possible! :eek:
...any ideas? :confused:
::] krycek [::
joh6nn
11-18-2002, 06:40 PM
well, stop me if i'm wrong, but doesn't 4! give you the number of possibler permutations, only if all the characters in the string are unique?
for the sake of demonstration, i'll represent a string as an array.
string1 = ["a","b","c","d"];
string2 = ["a","a","b","b"];
string3= "";
if you manipulate string one, then
string3 = string1[0] + string1[1] + string1[2] + string1[3];
string3 = string1[1] + string1[0] + string1[2] + string1[3];
that's two different combinations. but if you manipulate string two then it's only one combination, because it doesn't matter which "a" comes first.
in cases where letters repeat, in order to find the true number of possible combinations, then you have to assign discovered combinations to an array, and check all output against the values in that array, to make sure you haven't already come up with that.
i don't know how this effects what you're trying to do, if at all, but bad as i am at math, i wanted to make sure that i'm not mistaken in my understanding of this.
krycek
11-18-2002, 07:11 PM
hmmm, good point - and very true
the letters will not all be unique, so I suppose that the number given by 4! (is a factorial the sum of, say, 5*4*3*2*1? I forget a lot of the math I used to know!) will actually be MORE than the number of different possible combinations...
...and yet, does that really matter, because surely I would still have to calculate them in order to see if they have already been done? Are you with me so far...?
Because if I have to calculate them just to see if I have already calculated them, then there is no point, I could simply stick to looking through *every* possible combination...
What appeals to me is the idea that somehow an formula/function could be used to ONLY calculate the unique combinations, although I cannot for the life of me think how...
What I am basically trying to do here is come up with an "unsort" function, without having to store transformation data for each and every character. I am hoping that somehow the original string can be expressed as a function/equation of the sorted string... so that I can recreate the original, by having just the sorted string and the transformation data which would be the function/expression. It is important that the data not be too long, though, else it becomes pointless!
...any further thoughts? I am trying a lot of ideas but coming up blank, my math is not all that good in this area, and so if there are any expert mathematicians out there...?
::] krycek [::
Think recursive. This is *close* to what want, but with 2 conditions:
1. It calculates some permutations twice. I am trying to figure out why at the moment, and is probably just a simple logic error or off-by-one.
2. This is in C++. I wrote it in C++ simply because I have a nice debugger, and I have used C++ for recursion more often than in JS. Easy enough to convert, just replace the cout statements with a command to load it into a global array.
#include "apvector.h"
#include "apstring.h"
void permute(apstring, int);
apstring swap(apstring, int, int);
apstring swap(apstring str, int a, int b) {
char temp = str[a];
str[a] = str[b];
str[b] = temp;
return str;
}
void permute(apstring str, int offset) {
apvector<apstring> permutations(str.length());
if (offset < str.length()-1) {
for (int i = offset; i < str.length(); i++) {
permutations[i-offset] = swap(str, offset, i);
cout << permutations[i-offset] << endl;
permute(permutations[i-offset], offset+1);
cout << "---" << endl;
}
}
}
int main() {
apstring input;
cout << "String to permute?: ";
cin >> input;
permute(input, 0);
cin >> input;
return 0;
}
I'll work on it some more today, as it seems like an interesting application.
Some sample output:
String to permute?: abc
abc
abc
---
acb
---
---
bac
bac
---
bca
---
---
cba
cba
---
cab
---
---
And a Javascript swap function that does the same as the one in this program:
function swap(str, a, b) {
if (a == b)
return str;
else
return str.substring(0, a) + str.charAt(b) + str.substring(a+1, b) + str.charAt(a) + str.substr(b+1);
}
krycek
11-18-2002, 07:52 PM
hmmm... that looks pretty good...
however, would it be at all possible to use that technique to build a function that would work out the sorted string as an expression of the original?
I think I have to delve into matrix transformations here, but it is a long time since I did them, and I am not sure where to start.
My thought is like this:
if A is the original string, and B is the sorted equivalent, then somehow if I make a virtual matrix out of A and B, I *should* be able to express A as a function of B.
Hence, by applying the transformation to B, I can essentially "unsort" B to reform A.
However, I have no idea if what I am trying is even mathematically possible! (sigh!)
..it looks as though you may be on the right track, though, jkd, and I appreciate the time you are putting into this :)
::] krycek [::
You want to unsort a sorted string?
... You'll have to remember the current place in relation to the original place for each character.
Really nothing too complicated about it...
Say we have:
"cab" --> "abc"
var relation = [1, 2, 0];
The "a" was at position 1, the "b" was at position 2. and the "c" was at position 1.
And just rebuild the string by taking the nth element in that array and inserting nth character of the sorted string into that position inside a new string.
krycek
11-18-2002, 09:45 PM
um, that's right... however, the whole point of this exercise is to compress the data, you see. If I sort a string, then RLE it, it will be tiny. However, the key is to unsort it again in order to get the data back!
Therefore, I am trying to express one string as a function of the other, rather than storing the original positions. Simply because, if I store the original positions, then the data will get larger!
Now, if it is possible to store those positions and then compress that data... but no, because it is essentially the same (random) data.
Another idea I had is to take the char codes of the original string, put them together in a string, do the same with the sorted string, and then divide the original by the sorted char codes.
The original can then be reformed by multiplying the sorted string codes by the number given by the division. However, another problem arises, because the number of digits needed to be kept is essentially the same as the number of digits in the original char code string... hence, no compression again.
That is why I feel the key is in either A) using a matrix transformation, or B) some other function (yes, very vague!)
I have tried modifying the matrix transformations developed by Burrows and Wheeler at DEC (BWT) but with no success, I am simply not very good at matrices.
I do not even know if what I am trying to do is possible; I can do it be using permutations (such as you helped me to do earlier) and counting the permutations, and then applying that in reverse... but although extremely good compression, it is intensely processor-heavy and simply not a feasible method. Now, if I could somehow express the 'difference' in permutations from the original string to the sorted string, I think as a function or something, that could work... but again, is it mathematically possible?
My main area of maths involves geometry and calculus, not permutations, series, etc. And definitely not matrices!
So, you get what I am trying to do... what do you think?
::] krycek [::
scroots
11-19-2002, 08:05 PM
a little thought, it may help.
something along the lines of
sequence A:
nmty
rearrange becomes sequence B:
mnyt
instruction === sequence after instruction
move y to the left (+1) === mnyt
move m to the left (+1) === nmyt
or
move t to the right (-1) === mnyt
move n to the right (-1) === nmyt
other the other way(same method differently shown) is
Position 1 2 3 4
Sequence A n m t y
Sequence B m n y t
so position (p)
steps
1)p4 to p3
2)p2 to p1
or:
Position 1 2 3 4
Sequence A n m t y
Sequence B m n y t
the programmers dodgy way, each sequence is in a different box. so in the form sequence position A to sequence to postion B
1)A1 to B2
2)A2 to B1
3)A3 to B4
4)A4 to B3
i think the last method is the best way to get the movement using some script to find the position of the letter in sequence A and find the position of the letter in sequence B.
so to rearrange it back to order, so B becomes A just reverse the instructions so:
1)B1 to A2
2)B2 to A1
3)B3 to A4
4)B4 to A3
scroots
krycek
11-19-2002, 09:34 PM
...but how would that compress the data? :confused:
::] krycek [::
scroots
11-20-2002, 08:19 PM
it wouldn`t it would be a fixed way of recording transformations.
how long is the string you wish to compress? what does it consist of (alpha numeric?)
scroots
krycek
11-20-2002, 09:15 PM
the chars are determined by the 16-bit Unicode set... so, 65,536 possible chars.
I was hoping that by experimenting with matrices, recursion, permutations etc. that it would be possible to come up with some clever code that would find a function to describe one string (or set of numbers, depends how you look at it) as an expression of the other.
I do not know if that is possible, probably not, so after some playing around with it, I have returned to the compression method that I know works fine :) (nearly finished, too!)
::] krycek [::
vBulletin® v3.8.2, Copyright ©2000-2012, Jelsoft Enterprises Ltd.