Is there a way to generate various combinations of a String using specified replacements in JavaScript?

I am looking to find all possible combinations of a string while keeping the correct order intact and avoiding duplicates. The goal is to create more flexible solutions for Japanese quizzes by allowing a mix of kana and kanji characters. To achieve this, I need to generate all possible combinations for comparison with the user's input.

Here is the current syntax of the function: (located here)

Genki.getAlts('{月曜日}と{水曜日}と{金曜日}に{日本語}のクラスがあります', 'げつようび|すいようび|きんようび|にほんご');
    

The text within curly braces will be replaced by alternative text in the second argument, referred to as replacements. However, each alternate text should only replace the corresponding index. For example:

  • 月曜日 can only be replaced with げつようび
  • 水曜日 can only be replaced with すいようび
  • and so on...

For instance, if we have the following:

Genki.getAlts('...{A}...{B}...', '1|2', true);
    

I want it to produce various combinations, such as:

'...1...{B}...'
    '...1...2...'
    '...{A}...2...'
    '...{A}...{B}...'
    

The current function works effectively with 2-7 replacements, but when handling more than 8 replacements, some combinations are missed. The total number of combinations can be calculated using the formula: Math.pow(2, 8), yielding "256" combinations for 8 replacements, yet the getAlts() function currently returns only 234 combos, resulting in a coverage of 91%.

This is where I am facing challenges. I created the code independently, trying my best to include as many combinations as possible, but I believe there might be a simpler approach that I am missing due to my limited math skills.

To illustrate a case where the algorithm falls short, open your console and you may encounter a warning related to the last problem:

234/256 (91.40625% combo coverage for 8 replacements; 22 missing combos

Problematic code snippet:

Genki.getAlts('{1:私}はきのう{学校}で{1:写真}を{1:撮}りました。{2:私}は{家}でも{2:写真}を{2:撮}りました。', 'わたし|がっこう|しゃしん|と|わたし|いえ|しゃしん|と', true);
    

And a straightforward example involving 10 replacements for testing purposes:

Genki.getAlts('{A}{B}{C}{D}{E}{F}{G}{H}{I}{J}', '1|2|3|4|5|6|7|8|9|10', true)
    

Is there a simple method to retrieve all combinations for a string regardless of the specified number of replacements? While I understand the number of combinations using Math.pow(2, n), I am unsure how to systematically generate them all.

I am open to suggestions regarding existing algorithms or frameworks that could address this challenge.

PS: The current implementation functions well up to 7 replacements, with issues arising beyond this limit. Although avoiding exceeding 7 would be ideal, it is not always feasible. Moreover, the current approach used may not be optimal, hence the desire to improve upon it.

Answer №1

To tackle this issue, you can utilize binary mathematics. Below is a method that creates an array of strings:

function getAlts(str, alt) {
  var subs = alt.split('|');
  var length = subs.length;
  var permutations = Math.pow(2, length);
  var results = [];

  for (var i = 0; i < permutations; ++i) {
    var bitIndex = 0;
    var result = str.replace(/\{(.*?)\}/g, function (match, p1) {
      var subIndex = bitIndex++;
      var bit = length - 1 - subIndex;
      return ((1 << bit) & i) ? subs[subIndex] : p1;
    });

    results.push(result);
  }

  return results;
}

console.log(getAlts('...{A}...{B}...', '1|2'));

If you are using ES6 (ECMAScript 2015), you can opt to create a generator function, which consumes less memory:

function* getAlts(str, alt) {
  var subs = alt.split('|');
  var length = subs.length;
  var permutations = Math.pow(2, length);

  for (var i = 0; i < permutations; ++i) {
    var bitIndex = 0;
    var result = str.replace(/\{(.*?)\}/g, function (match, p1) {
      var subIndex = bitIndex++;
      var bit = length - 1 - subIndex;
      return ((1 << bit) & i) ? subs[subIndex] : p1;
    });

    yield result;
  }
}

var results = getAlts('{A}{B}{C}{D}{E}{F}{G}{H}{I}', '1|2|3|4|5|6|7|8|9');
var total = 0;

for (var result of results) {
  console.log(result);
  total++;
}

console.log('total:', total);

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

Exploring Facebook Graph API response with Angular 2 Mapping

I am using HTTP calls to access the Graph API in order to retrieve posts from a Facebook page. Here is the code snippet that fetches an array of posts: let url = 'https://graph.facebook.com/15087023444/posts?fields=likes.limit(0).summary(true),comme ...

Running the command npm show --outdated triggers an E404 error stating that the package is not found in this registry

I am currently working on a confidential project that I prefer not to make public. Despite using node v17.3.0 and npm 8.3.0, I am facing difficulties in displaying the outdated dependencies: $ npm show --outdated npm ERR! code E404 npm ERR! 404 Not Found - ...

What is the best method for transmitting server errors to the client?

When using passport.js, I have all the required code in place. However, I am facing an issue with displaying errors on the client-side. Despite having the successRedirect set up correctly, nothing happens when a wrong password is entered, and no error mess ...

Create a unique marker using the jsartoolkit5 library

I am working on a project involving Augmented Reality using jsartoolkit5 along with Three.js, and I am interested in incorporating a custom marker similar to the one demonstrated in this example. The markers are loaded into the project using the following ...

What is the best way to adjust an element to match the height of the browser window?

I've coded a solution to ensure that the height of a section (#home) matches the height of the window, but it's causing issues. Here is the code snippet I used: // Adjust Home section height based on window height function fitHomeToScreen() { ...

What is the best way to retrieve the default selected value in JavaScript and send it to PHP when the page is loaded?

Currently, I am facing an issue where I can only display the value as an output after manually selecting a Grade from the dropdown list on the page. However, I am looking to have the default selected Grade value displayed as an output when the page is init ...

What could be causing this error to occur in my JavaScript React code?

ERROR - '}' expected. Parse error. I'm experiencing issues with this code snippet where I try to fetch data for a graph using React, but I keep getting the parse error mentioned above. vehiculoPorColores = () => { const _this = this fet ...

Dynamically load current components in Angular 2's final release

In my quest to dynamically load a component in the upcoming release version 2.0.0, I encountered some challenges. Previously, in RC5, I utilized the following code for loading: I created a directive responsible for loading the controls: import { Check ...

Utilizing getUserMedia to capture portrait shots with the back camera

I am encountering an issue with starting the back camera in portrait mode using navigator.mediaDevices.getUserMedia in React. The camera does not appear to be taking into account the constraints I have set. Below is how the code looks for initialization: ...

Enhancing express functions with additional parameters in Node.JS

I am currently working on optimizing my node application by removing anonymous functions. An example of this is shown below: app.post('/page-edit.json', function (req, res) { db.get(req.body.page_id, function (err, doc) { res.content ...

Using PHP to ascertain the requested dataType or responseType from the client

My ajax request is fairly simple: $.post('server.php',data, function (json) {console.log(json)},'json'); I have configured jQuery to expect json data based on the dataType setting. Question: Is the dataType parameter equivalent to re ...

Prevent a HTML button from being clicked multiple times before it disappears (using Django)

I am currently working on a Django project that involves events where users can join by adding their user_id and event_id to the attend model. On the event page, there is a join button form that, when clicked, adds the user to the attendees list. After cli ...

What steps can be taken to address the error "console is undefined" in PowerShell?

I have a basic .js file saved on one of my drives that contains the following code: var x=3; function numSqaure(x) { return(x*x); } var sentence="The square of" + x + "is" + numSqaure(x); console.log(sentence); When attempting to run this script thro ...

The process of implementing sticky headers that stay in place while scrolling in a React application

I have a challenge with organizing tables based on date, using headers like (today, yesterday, last week, ...) and I want to make them sticky depending on the current table in the viewport. I attempted to implement this functionality using the react-sticky ...

Experiencing a lack of output when splitting a string using Selenium

Having trouble with a selenium javascript code that splits a string? Here's the specific code: <tr> <td>storeEval</td> <td>var dList = '${StaffAdminEmail}'.split('@'); </td> <td>dspl ...

Nested tabs in Bootstrap are not visible until they are re-selected

For my application, I am working on designing an admin panel that utilizes nested tabs. To give you a clear picture, here is a simple diagram illustrating how the tabs are structured: Initially Active and Visible -1a Initially Active and Visible -1b In ...

Ways to update state based on changes in localStorage values

Is there a way to update the state when the value of localStorage changes? For instance, I have a language switch button for French and English. When I click on English, it gets stored in localStorage. How can I ensure that the entire project switches to t ...

What is the best way to shorten a string that exceeds 50 pixels by replacing it with "..."?

Does anyone have a solution for a function in Javascript/jQuery that can replace part of a string wider than 50px with "..."? For example: Let's say I have a variable var="Theta Saving Non-Qualified Plan";. I'm looking to limit the length of t ...

Failure of Ajax POST requests to refresh screen content

Within my "scenario", I have numerous "forms" that consist of various "events," "data," and more. To populate all this information, I've included the following script to run once the page has fully loaded: $(document).ready(function() { var scenarioI ...

Trouble accessing Strapi CMS data on Next.js frontend using React.js

Currently, I am in the process of developing a website using Strapi as the CMS and Next.js(React) for the Frontend. The website features an image slider that includes an image, a headline, and a description. I am trying to retrieve these elements from my S ...