A bit complex challenge in Permutations for talented guys :)
Let's say we want to generate a Word using Placeholders (masks) for each part of the word.
In a word, we could have N Predefined placeholders (masks), let's call them Groups.
In each group we can have M values as options for the placeholder, let's call them Elements.
For instant, given a 3 parts word: [X][Y][Z].
[X] is a mask corresponding to the X Group. meaning each Element (value) from the X Group
will take place in the permutations word.
same for Y and Z.
A concrete example for the 3 parts word is 1a! out of 30 permutations of the following Groups and Elements below.
Please notice:
- Order is important, GroupX then GroupY and so..
- Group can have a "skip" option like Group "Y" in this example, which means that permutations should also include a word from the type: [X][Z]
- Total Permutations are Group1 X Group2 X G_n (or in this example GroupX X GroupY X GroupZ)
GroupX: 1, 2, 3
GroupY: a, b, c, d, Skip
GroupZ: !, #
All the 30 permutations for [X][Y][Z] are:
1a!, 1a#, 1b!, 1b#, 1c!, 1c#, 1d!, 1d#, 2a!, 2a#, 2b!, 2b#, 2c!, 2c#, 2d!, 2d#, 3a!, 3a#, 3b!, 3b#, 3c!, 3c#, 3d!, 3d#
And also because the "skip" of group Y we will have those permutations:
1!, 1#, 2!, 2#, 3!, 3#,
CodePudding user response：
Here's my code from this PAQ modified for chars:
import java.util.*;
import java.util.ArrayList;
class Main {
public static void main(String[] args) {
ArrayList<ArrayList<Character>> conditions = new ArrayList<ArrayList<Character>>();
ArrayList<Character> condition1 = new ArrayList<Character>();
condition1.add('1');
condition1.add('2');
condition1.add('3');
conditions.add(condition1);
ArrayList<Character> condition2 = new ArrayList<Character>();
condition2.add('a');
condition2.add('b');
condition2.add('c');
condition2.add('d');
condition2.add('\0');
conditions.add(condition2);
ArrayList<Character> condition3 = new ArrayList<Character>();
condition3.add('!');
condition3.add('#');
conditions.add(condition3);
System.out.println("Input Data:");
display(conditions);
System.out.println();
ArrayList<ArrayList<Character>> combos = findOptimalPairs(conditions);
System.out.println("Output Data:");
display(combos);
}
public static void display(ArrayList<ArrayList<Character>> data) {
for(ArrayList<Character> set : data) {
for(int i=0; i<set.size(); i ) {
System.out.print(set.get(i));
}
System.out.println();
}
}
public static ArrayList<ArrayList<Character>> findOptimalPairs(ArrayList<ArrayList<Character>> conditions) {
ArrayList<ArrayList<Character>> combos = new ArrayList<ArrayList<Character>>();
int combinations = 1;
int[] setSize = new int[conditions.size()];
for(int i=0; i<conditions.size(); i ) {
ArrayList<Character> set = conditions.get(i);
int size = set.size();
setSize[i] = size;
combinations = combinations * size;
}
int[] counters = new int[setSize.length];
for(int i=0; i<combinations; i ) {
ArrayList<Character> combo = new ArrayList<Character>();
for(int j=0; j<counters.length; j ) {
combo.add(conditions.get(j).get(counters[j]));
}
combos.add(combo);
for(int j=0; j<counters.length; j ) {
if (counters[j]<(setSize[j]-1)) {
counters[j] ;
break;
}
else {
counters[j] = 0;
}
}
}
return combos;
}
}
Producing the output:
Input Data:
123
abcd
!#
Output Data:
1a!
2a!
3a!
1b!
2b!
3b!
1c!
2c!
3c!
1d!
2d!
3d!
1!
2!
3!
1a#
2a#
3a#
1b#
2b#
3b#
1c#
2c#
3c#
1d#
2d#
3d#
1#
2#
3#
CodePudding user response：
Here is one solution that I thought of.
any ideas for performance optimization?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
public class WordGen
{
public WordGen(string[][] Options)
{
this.options = Options;
this.words = new List<string>();
this.optionsCounter = countAllOptions();
}
private string[][] options;
private long optionsCounter;
private Dictionary<int, int> optionsPointers;
private bool endofOptions;
private List<string> words;
private long countAllOptions()
{
long optionsCount = 1;
foreach (string[] g in options)
{
optionsCount *= g.Length;
}
return optionsCount;
}
private void intOptionPointers()
{
optionsPointers = new Dictionary<int, int>();
for (int i = 0; i <= options.Length - 1; i )
{
optionsPointers.Add(i, 0);
}
}
private void zeroOptionsPointers()
{
for (int i = options.Length - 1; i >= 0; i--)
{
if (optionsPointers[i] == options[i].Length - 1)
{
if (i == 0)
endofOptions = true;
else
optionsPointers[i] = 0;
}
else
{
optionsPointers[i] ;
return;
}
}
}
private void removeSkipChars()
{
IEnumerable<string> wordsWithsSkipChars = this.words.Where(w => w.Contains('-'));
foreach (string word in wordsWithsSkipChars)
{
int index = words.IndexOf(word);
words[index] = word.Trim('-');
}
}
private void buildWordsRec(StringBuilder word, int grpIndx)
{
int grpIndex = grpIndx;
while (!this.endofOptions)
{
//last group
if (grpIndex == options.Length - 1)
{
string fullWord = word.ToString() options[grpIndex][optionsPointers[grpIndex]];
words.Add(fullWord);
System.Console.WriteLine("word: " fullWord " as " words.Count " out of " this.optionsCounter);
//last element
if (optionsPointers[grpIndex] == options[grpIndex].Length - 1)
{
word.Clear();
zeroOptionsPointers();
grpIndex = 0;
}
else
{
optionsPointers[grpIndex] ;
}
}
else
{
word.Append(options[grpIndex][optionsPointers[grpIndex]]);
grpIndex ;
}
}
}
public List<string> GenerateWords()
{
StringBuilder word = new StringBuilder();
intOptionPointers();
buildWordsRec(word, 0);
removeSkipChars();
this.endofOptions = false;
return words;
}
public void WriteWordsToFile(string path)
{
System.IO.File.AppendAllLines(path, this.words);
}
public List<string> Words
{
get { return words; }
}
}
internal class Program
{
static void Main(string[] args)
{
string[] group1 = new string[] { "1","2","3" };
string[] group2 = new string[] { "a", "b", "c", "d", "-" };//"-" is act as Skip keyword
string[] group3 = new string[] { "!", "#"};
string[][] options = new string[][] { group1, group2, group3 };
WordGen pw = new WordGen(options);
pw.GenerateWords();
pw.WriteWordsToFile("D:\\words.txt");
System.Console.Read();
}
}