2

How to write a logic to display all possible "N" digit combinations of "A" & "B" where "A" and "B" forms a pair and "B" can only be inserted if we already have a non paired "A".

For ex : 

when N=2, output should be ["AB"]   
when N=4, output should be ["AABB","ABAB"]  
when N=6, output should be ["AAABBB","AABBAB","AABABB","ABABAB","ABAABB"]
zx8754
  • 52,746
  • 12
  • 114
  • 209
mak
  • 63
  • 3
  • 1
    What have you tried? Also, can you explain more? I don't understand what you mean by "forms a pair" (equal numbers of As and Bs?) or what a "non-paired A". Why are "ABBA", "BAAB", "BABA", "BBAA" not included in the n = 4 output? – Gregor Thomas Jul 03 '17 at 19:07
  • Totally lost with the question .. – BENY Jul 03 '17 at 19:20
  • This question is a bit unclear, @mak. Do you mean that only a certain number of B's can be added to match the same number of A's already existing in the string? – wake_wake Jul 03 '17 at 19:32
  • 1
    as far as I understand it, you can only add a B if there are more As than Bs before that (i.e. there is an A that does not have a B "partner" yet) . That's why BBAA and BABA and BAAB don't work bc the first B does not have an "unpaired" A. @mak , can you confirm and clarify your original post? – friep Jul 03 '17 at 20:13
  • @Gregor I think Bs should follow pattern of A, hence always starts with A. In case of N=4 "ABBA" is wrong, as 1st A then B, then should come A, then B. – zx8754 Jul 03 '17 at 20:20
  • 1
    @zx8754 that seems mostly right, but then why is "AABABB" valid? – Gregor Thomas Jul 03 '17 at 20:48
  • @Gregor phew, no idea, OK, voting to close as unclear. – zx8754 Jul 03 '17 at 21:14
  • 1
    Here's my guess: (1) Treat `{N = 2} => {"AB"}` as base case. (2) For N > 2, think iteratively. You can insert "AB" into any of the `{N - 2}` sets either (i) at the beginning of the string, (ii) after any A in the string, or (iii) at the end of the string. – Gregor Thomas Jul 03 '17 at 22:07

1 Answers1

3

I believe this should get you what you are looking for.

# Number of combinations
n <- 6

# Create dataframe of all combinations for 1 and -1 taken n number of times
# For calculations 1 = A and -1 = B
df <- expand.grid(rep(list(c(1,-1)), n))

# Select only rows that have 1 as first value
df <- df[df[,1] == 1,]

# Set first value for all rows as "A"
df[,1] <- "A"

# Set value for first calculation column as 1
df$s <- 1

# Loop through all columns starting with 2
for(i in 2:n){
  # Get name of current column
  cur.col <- colnames(df)[i]

  # Get the difference between the number of 1 and -1 for current column and the running total
  df$s2 <- apply(df[,c(cur.col,"s")], 1, sum)

  # Remove any rows with a negative value
  df <- df[df$s2 >= 0,]

  # Set running total to current total
  df$s <- df$s2

  # Set values for current column
  df[,i] <- sapply(as.character(df[,i]), switch, "1" = "A", "-1" = "B")

  # Check if current column is last column
  if(i == n){
    # Only select rows that have a total of zero, indicating that row has a pairs of AB values
    df <- df[df$s2 == 0, 1:n]
  }
}

# Get vector of combinations
combos <- unname(apply(df[,1:n], 1, paste0, collapse = ""))
Matt Jewett
  • 3,249
  • 1
  • 14
  • 21