Dada una string s, imprima todas las subsecuencias posibles de la string dada de manera iterativa. Ya hemos discutido el método recursivo para imprimir todas las subsecuencias de una string .
Ejemplos:
Input : abc Output : a, b, c, ab, ac, bc, abc Input : aab Output : a, b, aa, ab, aab
Enfoque 1:
Aquí, discutimos un enfoque iterativo mucho más fácil y simple que es similar a Power Set . Usamos un patrón de bits de la representación binaria de 1 a 2^longitud(es) – 1.
entrada = «abc»
Representación binaria para considerar 1 a (2^3-1), es decir, 1 a 7.
Comience de izquierda (MSB) a derecha (LSB) de la representación binaria y agregue caracteres de la string de entrada que corresponde al valor de bit 1 en representación binaria a la string de subsecuencia final sub.
Ejemplo:
001 => abc . Only c corresponds to bit 1. So, subsequence = c. 101 => abc . a and c corresponds to bit 1. So, subsequence = ac. binary_representation (1) = 001 => c binary_representation (2) = 010 => b binary_representation (3) = 011 => bc binary_representation (4) = 100 => a binary_representation (5) = 101 => ac binary_representation (6) = 110 => ab binary_representation (7) = 111 => abc
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all Subsequences
// of a string in iterative manner
#include <bits/stdc++.h>
using namespace std;
// function to find subsequence
string subsequence(string s, int binary, int len)
{
string sub = "";
for (int j = 0; j < len; j++)
// check if jth bit in binary is 1
if (binary & (1 << j))
// if jth bit is 1, include it
// in subsequence
sub += s[j];
return sub;
}
// function to print all subsequences
void possibleSubsequences(string s){
// map to store subsequence
// lexicographically by length
map<int, set<string> > sorted_subsequence;
int len = s.size();
// Total number of non-empty subsequence
// in string is 2^len-1
int limit = pow(2, len);
// i=0, corresponds to empty subsequence
for (int i = 1; i <= limit - 1; i++) {
// subsequence for binary pattern i
string sub = subsequence(s, i, len);
// storing sub in map
sorted_subsequence[sub.length()].insert(sub);
}
for (auto it : sorted_subsequence) {
// it.first is length of Subsequence
// it.second is set<string>
cout << "Subsequences of length = "
<< it.first << " are:" << endl;
for (auto ii : it.second)
// ii is iterator of type set<string>
cout << ii << " ";
cout << endl;
}
}
// driver function
int main()
{
string s = "aabc";
possibleSubsequences(s);
return 0;
}
Java
// Java program to print all Subsequences
// of a String in iterative manner
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
class Graph{
// Function to find subsequence
static String subsequence(String s,
int binary,
int len)
{
String sub = "";
for(int j = 0; j < len; j++)
// Check if jth bit in binary is 1
if ((binary & (1 << j)) != 0)
// If jth bit is 1, include it
// in subsequence
sub += s.charAt(j);
return sub;
}
// Function to print all subsequences
static void possibleSubsequences(String s)
{
// Map to store subsequence
// lexicographically by length
SortedMap<Integer,
HashSet<String>> sorted_subsequence = new TreeMap<Integer,
HashSet<String>>();
int len = s.length();
// Total number of non-empty subsequence
// in String is 2^len-1
int limit = (int) Math.pow(2, len);
// i=0, corresponds to empty subsequence
for(int i = 1; i <= limit - 1; i++)
{
// Subsequence for binary pattern i
String sub = subsequence(s, i, len);
// Storing sub in map
if (!sorted_subsequence.containsKey(sub.length()))
sorted_subsequence.put(
sub.length(), new HashSet<>());
sorted_subsequence.get(
sub.length()).add(sub);
}
for(Map.Entry<Integer,
HashSet<String>> it : sorted_subsequence.entrySet())
{
// it.first is length of Subsequence
// it.second is set<String>
System.out.println("Subsequences of length = " +
it.getKey() + " are:");
for(String ii : it.getValue())
// ii is iterator of type set<String>
System.out.print(ii + " ");
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
String s = "aabc";
possibleSubsequences(s);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to print all Subsequences
# of a string in iterative manner
# function to find subsequence
def subsequence(s, binary, length):
sub = ""
for j in range(length):
# check if jth bit in binary is 1
if (binary & (1 << j)):
# if jth bit is 1, include it
# in subsequence
sub += s[j]
return sub
# function to print all subsequences
def possibleSubsequences(s):
# map to store subsequence
# lexicographically by length
sorted_subsequence = {}
length = len(s)
# Total number of non-empty subsequence
# in string is 2^len-1
limit = 2 ** length
# i=0, corresponds to empty subsequence
for i in range(1, limit):
# subsequence for binary pattern i
sub = subsequence(s, i, length)
# storing sub in map
if len(sub) in sorted_subsequence.keys():
sorted_subsequence[len(sub)] = \
tuple(list(sorted_subsequence[len(sub)]) + [sub])
else:
sorted_subsequence[len(sub)] = [sub]
for it in sorted_subsequence:
# it.first is length of Subsequence
# it.second is set<string>
print("Subsequences of length =", it, "are:")
for ii in sorted(set(sorted_subsequence[it])):
# ii is iterator of type set<string>
print(ii, end = ' ')
print()
# Driver Code
s = "aabc"
possibleSubsequences(s)
# This code is contributed by ankush_953
C#
// C# program to print all Subsequences
// of a String in iterative manner
using System;
using System.Collections.Generic;
class Graph {
// Function to find subsequence
static string subsequence(string s, int binary, int len)
{
string sub = "";
for (int j = 0; j < len; j++)
// Check if jth bit in binary is 1
if ((binary & (1 << j)) != 0)
// If jth bit is 1, include it
// in subsequence
sub += s[j];
return sub;
}
// Function to print all subsequences
static void possibleSubsequences(string s)
{
// Map to store subsequence
// lexicographically by length
SortedDictionary<int, HashSet<string> >
sorted_subsequence
= new SortedDictionary<int, HashSet<string> >();
int len = s.Length;
// Total number of non-empty subsequence
// in String is 2^len-1
int limit = (int)Math.Pow(2, len);
// i=0, corresponds to empty subsequence
for (int i = 1; i <= limit - 1; i++) {
// Subsequence for binary pattern i
string sub = subsequence(s, i, len);
// Storing sub in map
if (!sorted_subsequence.ContainsKey(sub.Length))
sorted_subsequence[sub.Length]
= new HashSet<string>();
sorted_subsequence[sub.Length].Add(sub);
}
foreach(var it in sorted_subsequence)
{
// it.first is length of Subsequence
// it.second is set<String>
Console.WriteLine("Subsequences of length = "
+ it.Key + " are:");
foreach(String ii in it.Value)
// ii is iterator of type set<String>
Console.Write(ii + " ");
Console.WriteLine();
}
}
// Driver code
public static void Main(string[] args)
{
string s = "aabc";
possibleSubsequences(s);
}
}
// This code is contributed by phasing17
Javascript
<script>
// Javascript program to print all Subsequences
// of a string in iterative manner
// function to find subsequence
function subsequence(s, binary, len)
{
let sub = "";
for(let j = 0; j < len; j++)
// Check if jth bit in binary is 1
if (binary & (1 << j))
// If jth bit is 1, include it
// in subsequence
sub += s[j];
return sub;
}
// Function to print all subsequences
function possibleSubsequences(s)
{
// map to store subsequence
// lexicographically by length
let sorted_subsequence = new Map();
let len = s.length;
// Total number of non-empty subsequence
// in string is 2^len-1
let limit = Math.pow(2, len);
// i=0, corresponds to empty subsequence
for(let i = 1; i <= limit - 1; i++)
{
// Subsequence for binary pattern i
let sub = subsequence(s, i, len);
// Storing sub in map
if (!sorted_subsequence.has(sub.length))
sorted_subsequence.set(sub.length, new Set());
sorted_subsequence.get(sub.length).add(sub);
}
for(let it of sorted_subsequence)
{
// it.first is length of Subsequence
// it.second is set<string>
document.write("Subsequences of length = " +
it[0] + " are:" + "<br>");
for(let ii of it[1])
// ii is iterator of type set<string>
document.write(ii + " ");
document.write("<br>");
}
}
// Driver code
let s = "aabc";
possibleSubsequences(s);
// This code is contributed by gfgking
</script>
Producción
Subsequences of length = 1 are: a b c Subsequences of length = 2 are: aa ab ac bc Subsequences of length = 3 are: aab aac abc Subsequences of length = 4 are: aabc
Complejidad 
de tiempo: donde n es la longitud de la string para encontrar subsecuencias y l es la longitud de la string binaria.
Complejidad espacial: O(1)
Enfoque 2:
El enfoque es obtener la posición del bit establecido más a la derecha y restablecer ese bit después de agregar el carácter correspondiente de la string dada a la subsecuencia y repetirá lo mismo hasta que el patrón binario correspondiente no tenga bits establecidos.
If input is s = “abc” Binary representation to consider 1 to (2^3-1), i.e 1 to 7. 001 => abc . Only c corresponds to bit 1. So, subsequence = c 101 => abc . a and c corresponds to bit 1. So, subsequence = ac. Let us use Binary representation of 5, i.e 101. Rightmost bit is at position 1, append character at beginning of sub = c ,reset position 1 => 100 Rightmost bit is at position 3, append character at beginning of sub = ac ,reset position 3 => 000 As now we have no set bit left, we stop computing subsequence.
Ejemplo:
binary_representation (1) = 001 => c binary_representation (2) = 010 => b binary_representation (3) = 011 => bc binary_representation (4) = 100 => a binary_representation (5) = 101 => ac binary_representation (6) = 110 => ab binary_representation (7) = 111 => abc
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code all Subsequences of a
// string in iterative manner
#include <bits/stdc++.h>
using namespace std;
// function to find subsequence
string subsequence(string s, int binary)
{
string sub = "";
int pos;
// loop while binary is greater than 0
while(binary>0)
{
// get the position of rightmost set bit
pos=log2(binary&-binary)+1;
// append at beginning as we are
// going from LSB to MSB
sub=s[pos-1]+sub;
// resets bit at pos in binary
binary= (binary & ~(1 << (pos-1)));
}
reverse(sub.begin(),sub.end());
return sub;
}
// function to print all subsequences
void possibleSubsequences(string s){
// map to store subsequence
// lexicographically by length
map<int, set<string> > sorted_subsequence;
int len = s.size();
// Total number of non-empty subsequence
// in string is 2^len-1
int limit = pow(2, len);
// i=0, corresponds to empty subsequence
for (int i = 1; i <= limit - 1; i++) {
// subsequence for binary pattern i
string sub = subsequence(s, i);
// storing sub in map
sorted_subsequence[sub.length()].insert(sub);
}
for (auto it : sorted_subsequence) {
// it.first is length of Subsequence
// it.second is set<string>
cout << "Subsequences of length = "
<< it.first << " are:" << endl;
for (auto ii : it.second)
// ii is iterator of type set<string>
cout << ii << " ";
cout << endl;
}
}
// driver function
int main()
{
string s = "aabc";
possibleSubsequences(s);
return 0;
}
Python3
# Python3 program to print all Subsequences
# of a string in an iterative manner
from math import log2, floor
# function to find subsequence
def subsequence(s, binary):
sub = ""
# loop while binary is greater than
while(binary > 0):
# get the position of rightmost set bit
pos=floor(log2(binary&-binary) + 1)
# append at beginning as we are
# going from LSB to MSB
sub = s[pos - 1] + sub
# resets bit at pos in binary
binary= (binary & ~(1 << (pos - 1)))
sub = sub[::-1]
return sub
# function to print all subsequences
def possibleSubsequences(s):
# map to store subsequence
# lexicographically by length
sorted_subsequence = {}
length = len(s)
# Total number of non-empty subsequence
# in string is 2^len-1
limit = 2 ** length
# i=0, corresponds to empty subsequence
for i in range(1, limit):
# subsequence for binary pattern i
sub = subsequence(s, i)
# storing sub in map
if len(sub) in sorted_subsequence.keys():
sorted_subsequence[len(sub)] = \
tuple(list(sorted_subsequence[len(sub)]) + [sub])
else:
sorted_subsequence[len(sub)] = [sub]
for it in sorted_subsequence:
# it.first is length of Subsequence
# it.second is set<string>
print("Subsequences of length =", it, "are:")
for ii in sorted(set(sorted_subsequence[it])):
# ii is iterator of type set<string>
print(ii, end = ' ')
print()
# Driver Code
s = "aabc"
possibleSubsequences(s)
# This code is contributed by ankush_953
C#
// C# program to print all Subsequences
// of a string in an iterative manner
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// function to find subsequence
static string subsequence(string s, int binary)
{
string sub = "";
// loop while binary is greater than
while (binary > 0) {
// get the position of rightmost set bit
var pos = (int)Math.Floor(
Math.Log(binary & (-binary))
/ Math.Log(2))
+ 1;
// append at beginning as we are
// going from LSB to MSB
sub = s[pos - 1] + sub;
// resets bit at pos in binary
binary = (binary & ~(1 << (pos - 1)));
}
char[] charArray = sub.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
// function to print all subsequences
static void possibleSubsequences(string s)
{
// map to store subsequence
// lexicographically by length
Dictionary<int, HashSet<string> > sorted_subsequence
= new Dictionary<int, HashSet<string> >();
int length = s.Length;
// Total number of non-empty subsequence
// in string is 2^len-1
int limit = (int)Math.Pow(2, length);
// i=0, corresponds to empty subsequence
for (int i = 1; i < limit; i++) {
// subsequence for binary pattern i
string sub = subsequence(s, i);
// storing sub in map
if (sorted_subsequence.ContainsKey(
sub.Length)) {
sorted_subsequence[sub.Length].Add(sub);
}
else {
sorted_subsequence[sub.Length]
= new HashSet<string>();
sorted_subsequence[sub.Length].Add(sub);
}
}
foreach(var it in sorted_subsequence)
{
// it.first is length of Subsequence
// it.second is set<string>
Console.WriteLine("Subsequences of length = "
+ it.Key + " are:");
var arr = (it.Value).ToArray();
Array.Sort(arr);
for (int i = 0; i < arr.Length; i++) {
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main(string[] args)
{
string s = "aabc";
possibleSubsequences(s);
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to print all Subsequences
// of a string in an iterative manner
// function to find subsequence
function subsequence(s, binary)
{
var sub = "";
// loop while binary is greater than
while(binary > 0)
{
// get the position of rightmost set bit
var pos= Math.floor(Math.log2(binary&-binary) + 1);
// append at beginning as we are
// going from LSB to MSB
sub = s[pos - 1] + sub;
// resets bit at pos in binary
binary= (binary & ~(1 << (pos - 1)));
}
sub = sub.split("");
sub = sub.reverse();
return sub.join("");
}
// function to print all subsequences
function possibleSubsequences(s)
{
// map to store subsequence
// lexicographically by length
var sorted_subsequence = {};
var length = s.length;
// Total number of non-empty subsequence
// in string is 2^len-1
var limit = 2 ** length;
// i=0, corresponds to empty subsequence
for (var i = 1; i < limit; i++)
{
// subsequence for binary pattern i
var sub = subsequence(s, i);
// storing sub in map
if (sorted_subsequence.hasOwnProperty(sub.length))
{
//var list = sorted_subsequence[sub.length];
//list.push(sub);
sorted_subsequence[sub.length].push(sub);
}
else
sorted_subsequence[sub.length] = [sub];
}
for (const it in sorted_subsequence)
{
// it.first is length of Subsequence
// it.second is set<string>
console.log("Subsequences of length =", it, "are:");
var arr = sorted_subsequence[it];
arr.sort();
var set = new Set(arr);
for (const ii of set)
// ii is iterator of type set<string>
process.stdout.write(ii + " ");
console.log()
}
}
// Driver Code
var s = "aabc";
possibleSubsequences(s);
// This code is contributed by phasing17
Producción
Subsequences of length = 1 are: a b c Subsequences of length = 2 are: aa ab ac bc Subsequences of length = 3 are: aab aac abc Subsequences of length = 4 are: aabc
Complejidad de tiempo : 
donde n es la longitud de la string para encontrar la subsecuencia yb es el número de bits establecidos en la string binaria.
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Abhishek rajput y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA