javascript string algorithm

Question

Let's say I have a string variable called myString, and another string variable called myChar.

var myString = "batuhan"; // it's user input.
var myChar = "0"; // will be one character, always

What I need is, a function that returns all the combinations of myString and myChar.

Like:

"batuhan","batuha0n","batuh0an","batuh0a0n","batu0han","batu0ha0n","batu0h0an","batu0h0a0n","bat0uhan","bat0uha0n","bat0uh0an","bat0uh0a0n","bat0u0han","bat0u0ha0n","bat0u0h0an","bat0u0h0a0n","ba0tuhan","ba0tuha0n","ba0tuh0an","ba0tuh0a0n","ba0tu0han","ba0tu0ha0n","ba0tu0h0an","ba0tu0h0a0n","ba0t0uhan","ba0t0uha0n","ba0t0uh0an","ba0t0uh0a0n","ba0t0u0han","ba0t0u0ha0n","ba0t0u0h0an","ba0t0u0h0a0n","b0atuhan","b0atuha0n","b0atuh0an","b0atuh0a0n","b0atu0han","b0atu0ha0n","b0atu0h0an","b0atu0h0a0n","b0at0uhan","b0at0uha0n","b0at0uh0an","b0at0uh0a0n","b0at0u0han","b0at0u0ha0n","b0at0u0h0an","b0at0u0h0a0n","b0a0tuhan","b0a0tuha0n","b0a0tuh0an","b0a0tuh0a0n","b0a0tu0han","b0a0tu0ha0n","b0a0tu0h0an","b0a0tu0h0a0n","b0a0t0uhan","b0a0t0uha0n","b0a0t0uh0an","b0a0t0uh0a0n","b0a0t0u0han","b0a0t0u0ha0n","b0a0t0u0h0an","b0a0t0u0h0a0n"

Rules: myChar shouldn't follow myChar

How can I do that? Really my brain dead right now :/

What have you tried? Questions like this should show that you did some basic research into the problem and show what you tried and where you got stuck. Hint, look at `.slice()`. Also, is this homework? Because if it is, that changes how the help should be offered (with an emphasis on teaching). — jfriend00, May 09 '15 at 19:45
@jfriend00 I couldn't build the algorithm even in my mind. Any hints at the algorithm part? — BTHN, May 09 '15 at 19:46
How many instances of `myChar` are allowed in the result and can they be consecutive and are all characters of `myString` always used and always kept in the same order? Is `myChar` always only a single character? You haven't even described the problem in enough detail to know how to approach it. If `myChar` can only be used once in the result, then there are only `myString.length + 1` possible positions for `myChar` to go in the result. — jfriend00, May 09 '15 at 19:46
Depends of the myString, but myChar shouldn't follow myChar. — BTHN, May 09 '15 at 19:49
You need to edit your question and put a much more complete description of the rules in the question that covers all possible issues with the value of `myString` and the value of `myChar`. Is this homework? The question is currently incomplete as it stands. — jfriend00, May 09 '15 at 19:50
No, It's not homework. I need it for my side project. I'll edit main post, sorry for the missing details. — BTHN, May 09 '15 at 19:52
So, you can have as many copies of myChar in the result as long as no two are in a row? So, `"0b0a0t0u0h0a0n0"` would be a legal result? And, is `myChar` always only a single character or might it be multiple characters? If multiple characters, then are its characters always kept together or can they be split too? Still lots of missing parts of the specification. FYI, it's a much easier problem if `myChar` is only a single character. — jfriend00, May 09 '15 at 19:54
yep it's legal. I edited the question, myChar will be single character every time. — BTHN, May 09 '15 at 19:56
As far as I understand you want to build a cartesian product. See this great, popular SO question: http://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript — roland, May 09 '15 at 19:52

score 0 · Answer 1 · answered May 09 '15 at 20:06

0

It's possible to implement what you want using recursion.

// Example: allCombinations("abcd", "0") returns the array
// ["abcd", "abc0d", "ab0cd", "ab0c0d", "a0bcd", "a0bc0d", "a0b0cd", "a0b0c0d"]
function allCombinations(str, chr) {
    if (str.length == 1)
        return [str];
    var arr = allCombinations(str.substring(1), chr);
    var result = [];
    var c = str.charAt(0);
    for (var i = 0; i < arr.length; i++)
        result.push(c + arr[i]);
    for (var i = 0; i < arr.length; i++)
        result.push(c + chr + arr[i]);
    return result;
}

answered May 09 '15 at 20:06

Nayuki

17,911
6
53
80

Thanks, it's working. How this recursion works, can you explain? – BTHN May 09 '15 at 20:10
What happened to the combinations where `chr` is first or last in the string and I think the OP said that `chr` can't be placed next to the same character in the source string so I don't see any checks for that case either. – jfriend00 May 09 '15 at 20:11
@jfriend00 I said it's working, i didn't mean it's true. But anyway I just want to learn how this recursion works. – BTHN May 09 '15 at 20:15
@BTHN - I'm asking Nayuki (not you) why their solution doesn't include some combinations that you said are required. My comment was not directed at you. Your question says you need "all" combinations that match the rules. This answer does not appear to yet return "all" combinations. – jfriend00 May 09 '15 at 20:17
My solution correctly reflects the sample output BTHN provided in the current version of the question. (Except that my items are not ordered by weight.) – Nayuki May 09 '15 at 20:18
@NayukiMinase - if you follow the comments, the OP said that `"0b0a0t0u0h0a0n0"` is a desired result too. The question is still far too vague as to exactly what the desired output is so I've had to ask many questions to try to figure it out. – jfriend00 May 09 '15 at 20:18
@jfriend00 dude sorry, I really didn't want to direct answer to this question. What I want is, learn how to think problems like this. NayukiMinase 's answer is so close, so I asked him to how this recursion works :) – BTHN May 09 '15 at 20:21
@BTHN - then your question should be been more about principles and concepts used to create combinations rather than a specific problem. You proposed a very specific problem that was missing many of the details required to know how to answer it. OK, sorry, I tried to just understand your question well enough to help. I'll leave now. I have no problem with you asking Nayuki for clarification, nor did I ever say anything about that. – jfriend00 May 09 '15 at 20:25

score 0 · Answer 2 · answered May 09 '15 at 20:26

You may or may not have noticed this but this is basically counting in binary. If we define bit 0 to be the absence of myChar and bit 1 to be the presence of myChar, then the following sequence:

var myString = ".....";
var myChar = "1";

var sequence = [
    ".....1",
    "....1.",
    "....1.1",
    "...1.."
];

is basically counting from 1 to 4 in binary:

var sequence = [
    0b0000001,
    0b0000010,
    0b0000011,
    0b0000100
];

Therefore, all you need is a for loop to count up to the bit amount of the length of the string plus 1 (because the position at the end of the string is also legal):

var len = Math.pow(2,myString.length+1);
for (var x = 0; x < len; x++) {
    // x in binary is all the possible combinations
    // now use the "1" bits in x to modify the string:

    // Convert myString to array for easy processing:
    var arr = myString.split('');
    arr.push(""); // last position;

    for (var i = myString.length; i >= 0; i--) {
        if ((x >> i) & 0x01) { // check if bit at position i is 1
            arr[i] = myChar + arr[i];
        }
    }

    console.log(arr.join('')); // print out one combination
}

Of course, this works only for small strings of up to 31 characters. For larger strings you'd need to do the binary counting using things other than numbers. Doing it in a string form is one option. Another option is to use a bigint library such as BigInteger.js to do the counting.

In general, recursion is the general way to solve these sorts of problems. But in some cases like this specific case there may be other solutions. The key is to be able to identify patterns in what you're trying to generate. Even if you use recursion, you need to identify the pattern of the output. If you identify the pattern and it reminds you of some other algorithm then that's a bonus. — slebetman, May 09 '15 at 20:40

javascript string algorithm

2 Answers2