Вычисление перестановок строки, где имеют значение предшествующие символы

Question

У меня есть начальная строка: BBBCCC.

Где B is +1 и C is -1

правило: C не может быть помещен, если суммарные значения B's and C's предыдущих его приведут к отрицательному числу.

Например, BCCBBC не может работать, так как у нас есть +1 - 1 (0) -1 (-1) +1 (0) +1 (1) -1 (0), так как это приводит к отрицательному числу во время накопления.

Это означает, что принятые перестановки будут следующие:

BBBCCC BBCBCC BBCCBC BCBBCC BCBCBC

У меня есть несколько идей кода, но я не уверен, что это хороший способ, чтобы начать это с заданной вычисленной строкой N начальный B s будет.

Я пытаюсь реализовать это на Java.

То, что я до сих пор:

import java.util.ArrayList; 
import java.util.Scanner; 

public class Main { 

    private static ArrayList<String> pathPermutations = new ArrayList<String>(); 

    public static void main(String[] args) { 
     int numToEnter; 
     Scanner myScanner = new Scanner(System.in); 
     System.out.println("Enter a node: "); 
     numToEnter = myScanner.nextInt(); 
     calculatePermutations(numToEnter); 
    } 


    public static void calculatePermutations(int nodeNum){ 
     pathPermutations.clear(); 
     pathPermutations.add(constructInitialPath(nodeNum)); 

     System.out.println(pathPermutations.get(0)); 
    } 
    public static String constructInitialPath(int nodeNum){ 
     String pathString = ""; 
     for(int i = 0; i<nodeNum*2;i++){ 
      if(i<nodeNum){ 
       pathString+="B"; 
      }else{ 
       pathString+="C"; 
      } 
     } 
     return pathString; 
    } 

    public void populatePermutations(String s){ 
     int length = s.length()/2; 
     int accumulator = 0; 
     int nodeIntercepts = 0; 
     String newPermutation = ""; 
     for(int i = 0; i<length*2;i++){ 
      if(i==0){ 
       newPermutation+="B"; 
       accumulator++; 
      }else if(i>0 && accumulator>){ 

      } 
     } 


    } 
} 

Как я могу манипулировать метод populatePermutations взять в исходной строке BBBCCC (или N произвольное число Б/C отсортирован) и рекурсивно вычислить подстроки в соответствии с мое правило было сказано ранее.

Например:

Шаг 1. BBBCCC Шаг 2. BBCBCC, и т.д. и т.п.

Answer 1

Вам нужен рекурсивный метод. До сих пор этот метод получал построенную строку, сумму букв и длину цели в качестве параметров.

• Если цель достигнута, распечатать результат и вернуться.
• Добавить +1 письмо, затем называть себя.
• Если это разрешено, добавьте вместо него -1-букву, а затем вызовите себя.

---

Или вместо целевой длины, числа +1 и -1 букв влево, чтобы добавить.