algorithm - una - wiegand 32 bits

Encuentre el número de bits que se voltearán para obtener un máximo de 1 en la matriz

Question

Tenemos una matriz de bits como abajo

{1 0 1 0 0 1 0 1}

El número de bits en la matriz anterior es 8

Si tomamos el rango de [1,5] entonces el número de bits en el rango de [1,5] es [0 1 0 0 1] .
Si cambiamos este rango, luego de voltearlo será [ 1 0 1 1 0]
Entonces, el número total de 1 después de cambiar el rango [1,5] es [1 1 0 1 1 0 0 1] = 5

Si tomamos el rango desde [1,6] entonces el número de bits en el rango [1,6] es [0 1 0 0 1 0] .
Si cambiamos este rango, luego de voltearlo será [ 1 0 1 1 0 1]
Entonces, el número total de 1 después de cambiar el rango [1,5] es [1 1 0 1 1 0 1 1] = 6

Así que la respuesta es rango [1,6] y después de voltear podemos obtener 6 1 en la matriz

¿Hay un buen algoritmo que pueda resolver este problema? Solo pienso en la programación dinámica porque este problema se puede dividir en problemas secundarios que se pueden combinar.

Answer 1

Aquí hay un enfoque recursivo: https://ideone.com/Su2Mmb

public static void main(String[] args) {
int [] input = {1, 0, 0, 1, 0, 0, 1,1,1,1, 0,1};
System.out.println(findMaxNumberOfOnes(input,0, input.length-1));
}
private static int findMaxNumberOfOnes(int[] input, int i, int j) {
if (i==j)
return 1;
int option1 = input[i] + findMaxNumberOfOnes(input, i+1, j);
int option2 = count(input , i , j, true);
int option3 = count(input, i, j, false);
int option4 =findMaxNumberOfOnes(input, i, j-1) +input[j];
return Math.max(option1, Math.max(option2,Math.max(option3,option4)));
}
private static int count(int[] input, int i, int j, boolean flipped) {
int a = flipped?0:1;
int count = 0;
while (i<=j){
count += (input[i++]==a)?1:0;
}
return count;
}

Answer 2

El siguiente código utiliza el algoritmo trivial y se ejecuta en O (n²).

#include <iostream>
#include <bitset>
#include <utility>
typedef std::pair<unsigned, unsigned> range_t;
template <std::size_t N>
range_t max_flip(const std::bitset<N>& bs){
int overall_score = 0;
range_t result = range_t{0,0};
for(std::size_t i = 0; i < N; ++i){
int score = bs[i] ? -1 : 1;
auto max = i;
for(std::size_t j = i + 1; j < N; ++j){
auto new_score = score + (bs[j] ? -1 : 1);
if(new_score > score){
score = new_score;
max = j;
}
}
if(score > overall_score){
overall_score = score;
result = {i,max};
}
}
return result;
}
int main(){
std::bitset<8> bitfield(std::string("10100101"));
range_t range = max_flip(bitfield);
std::cout << range.first << " .. " << range.second << std::endl;
}

Answer 3

Este problema se puede resolver utilizando la programación dinámica en tiempo y espacio lineal. Puede crear una matriz a la izquierda donde a la izquierda [i] es el número de 1 en el subarreglo 0 a i (inclusive). Así que para dos índices i y j:

case 1: i==j, result is array size sz-1 (if no 0 in array) or sz+1 (if there is at least one 0 in array)
case 2: i less than j, result is:
left[i-1] (# of 1 on subarray 0 ~ i-1) +
(j-i+1-(left[j]-left[i-1])) (# of 0 on subarray i ~ j) +
left[sz-1]-left[j] (# of 1 on subarray j+1 ~ sz-1)
this equals to: (j-2*left[j])-(i-2*left[i-1])+left[sz-1]+1

Por lo tanto, de acuerdo con el caso 2, necesitamos otra temperatura de matriz para almacenar por cada j min{i-2*left[i-1] where i<j}

Así que podemos atravesar la matriz, en cada índice j, calculamos el caso anterior dos (en tiempo constante) y actualizamos el resultado final si es más grande.

Mi código en c ++:

int func(vector<int>& arr){
int res = 0;
int sz = arr.size();
vector<int> left(sz, 0);
for(int i=0; i<sz; i++){
left[i] = (arr[i]==1?1:0)+(i==0?0:left[i-1]);
}
bool all_1 = true;
for(int i=0; i<sz; i++){
if(arr[i] == 0) all_1=false;
}
if(all_1) return sz-1;
res = left[sz-1]+1;
vector<int> temp(sz, INT_MAX);
for(int i=1; i<sz; i++)
temp[i] = min(temp[i-1], i-2*left[i-1]);
for(int j=1; j<sz; j++){
int val = j+1-left[j]+(left[sz-1]-left[j]);
val = max(val, j-2*left[j]-temp[j]+left[sz-1]+1);
res = max(res, val);
}
return res;
}

Answer 4

Inspirado por el comentario de @Nabbs, hay una manera fácil de resolver esto en tiempo lineal: reduciendo el problema a la suma máxima de segmentos.

Transforma todos los 0s a 1s y todos los 1s a -1s. El problema es, entonces, el mismo que minimizar la suma de la matriz después de la transformación. (la suma mínima contiene la mayoría de -1 en la matriz transformada, que corresponde a la mayoría de 1 en el problema original).

Podemos calcular la suma como

sum(after flipping) = sum(non-flipped) - sum(flipped part before flipping)

Porque la suma de la parte invertida está invertida. Si ahora expresamos la parte no volteada como sigue:

sum(non-flipped) = sum(original array) - sum(flipped part before flipping)

Nos encontramos con que tenemos que minimizar

sum(after flipping) = sum(original array) - 2 sum(flipped part before flipping)

La primera parte es una constante, por lo que realmente necesitamos maximizar la suma de la parte volteada. Esto es exactamente lo que hace el problema de suma de segmento máximo.

Escribí una larga derivación sobre cómo resolver ese problema en tiempo lineal hace un tiempo , así que ahora solo compartiré el código. A continuación actualicé el código para almacenar también los límites. Elegí javascript como idioma, porque es muy fácil de probar en el navegador y porque no tengo que hacer explícitos los tipos de variables x e y .

var A = Array(1, 0, 1, 0, 0, 1, 0, 1);
var sum = 0;
// count the 1s in the original array and
// do the 0 -> 1 and 1 -> -1 conversion
for(var i = 0; i < A.length; i++) {
sum += A[i];
A[i] = A[i] == 0 ? 1 : -1;
}
// find the maximum subarray
var x = { value: 0, left: 0, right: 0 };
var y = { value: 0, left: 0 };
for (var n = 0; n < A.length; n++) {
// update y
if (y.value + A[n] >= 0) {
y.value += A[n];
} else {
y.left = n+1;
y.value = 0;
}
// update x
if (x.value < y.value) {
x.left = y.left;
x.right = n;
x.value = y.value;
}
}
// convert the result back
alert("result = " + (sum + x.value)
+ " in range [" + x.left + ", " + x.right + "]");

Puedes verificar esto fácilmente en tu navegador. Por ejemplo, en Chrome, presione F12, haga clic en Consola y pegue este código. Debe salir

result = 6 in range [1, 4]

Answer 5

Intento 2.0 en O (n)

Comience al principio de la matriz. Paso a través de la matriz. Hasta que llegue a 0. Cuando llegue al primer 0, configure el conteo en 0, recuerde la posición de inicio y continúe avanzando mientras cuenta: +1 para 0 y -1 para 1. Si el conteo se vuelve negativo, reinicie el conteo y continúe hasta llegas al final Si encuentra otro conteo de conjuntos de cero a 0 y repita el algoritmo anterior. Al final, cambia el rango de las posiciones inicial y final, si las hay.

void Flip( int* arr , int len )
{
int s = -1 , e = -1 , c ;
for( int i = 0 ; i < len ; i++ )
{
if( arr[i] == 0 )
{
c = 0 ;
s = i ;
e = i ;
for( int j = i ; j < len ; j++ , i++ )
{
if( arr[i] == 0 )
c++ ;
else
c-- ;
if( c < 0 )
{
s = -1 ;
e = -1 ;
break ;
}
if( arr[i] == 0 )
e = i ;
}
}
}
if( s > -1 )
for( int i = s ; i <= e ; i++ )
arr[i] ^= 1 ;
for( int i = 0 ; i < len ; i++ )
printf("%d " , arr[i] ) ;
}
int main(void)
{
int a[13] = {1,0,1,1,0,0,1,0,1,1,0,1,0} ;
Flip( a , 13 ) ;
return 0;
}

No probado a fondo, puede haber errores (casos de borde) pero funciona en principio.

Answer 6

También pensé lo mismo que @this ha mencionado. Pero hay errores en su solución. Mi código después de corregir el error (ver explicación más abajo):

vector<int> Solution::flip(string arr) {
int s = -1 , e = -1 , c , len = arr.size(), S = -1, E = -1, Max = 0;
for( int i = 0 ; i < len ; i++ )
{
if( arr[i] == ''0'' )
{
c = 0 ;
s = i ;
e = i ;
for( int j = i ; j < len ; j++, i++ )
{
if( arr[j] == ''0'' )
c++ ;
else
c-- ;
//cout << c << " ";
if( c < 0 )
{
s = -1 ;
e = -1 ;
break ;
}
if( arr[j] == ''0'' )
e = i ;
if(c > Max){
S = s;
E = e;
Max = c;
}
}
}
}
vector<int> ans;
if( S > -1 ){
ans.push_back(S);
ans.push_back(E);
return ans;
}
else
return ans;

}

Explicación : Comience desde el principio de la matriz. Paso a través de la matriz. Hasta que llegue a 0. Cuando llegue al primer 0, establezca el conteo en 0, recuerde la posición de inicio y continúe presionando mientras cuenta: +1 para 0 y -1 para 1. Max almacena el valor de max (#zeros en todo el conjunto de [ s , e ]). Si c es mayor que Max entonces el conjunto actual [ s , e ] contiene el número máximo de bits ''0''. De ahí la actualización de Max, S, E, Si el conteo se vuelve negativo, significa que el número de ''1'' es mayor que el número de ''0'' en el conjunto [ s , e ], así que reinicie el conteo c , el inicio local s , el final local e . y continúa hasta llegar al final. Si encuentra otro conteo de conjuntos de cero a 0 y repita el algoritmo anterior. El valor final de S , E es el índice del rango en el que se van a invertir los bits. Si no existe tal rango (todos los bits son ''1'') entonces S = -1, E = - 1 .

Answer 7

 void maxones(int n)
{
int table[n+1][n+1], i, j, totalones = 0, max = INT_MIN, start_pos = 0, end_pos =0;
if(n == 0)
{
printf("Max no of ones from 0 to %d /n",sizeof(int) * 8 -1);
return;
}
/* size of (int) * 8 bits, calculate total no of ones in every bit */
for(i=0; i<sizeof(n) * 8; i++)
totalones += n & (1 >> i);
/* Base conditions to be filled */
for(i=0; i<n; i++)
table[i][i] = (n & (1 >> i)) ? totalones - 1 : totalones + 1;
for(i=0; i<n; i++ )
for(j=i+1; j<n; j++)
{
table[i][j] = table[i][j-1] + ( n & (1 >> j)) ? 0 : 1;
if (max < table[i][j])
{
max = table[i][j];
start_pos = i;
end_pos = j;
}
}
printf("Max no of Ones on fliping bits from pos %d to pos %d /n",start_pos, end_pos);
}
int main()
{
int n;
printf("Enter number %d /n", &n);
maxones(n);
return 0;
}