C++ проверить - можно ли из одной строки с помощью перестановок получить другую

напомню, что наше рассуждение начиналось здесь

для начала распишем логику алгоритма:
1) проверим что длины строк равны (используем эту функцию) - просто напишем что-то вроде

if (strlen(str1)==strlen(str2)) 
{// продолжаем работать}
else {} // прерываем работу программы

2) нам надо понять - достаточно ли необходимых символов во второй строке чтобы получить первую - с точки зрения логики (долго не думая) - это проще всего организовать вложив один цикл в другой:

  1. пробегаем циклом по одной из строк - пусть она называется "первая" строка
  2. внутри цикла перебора первой строки располагаем цикл перебора второй строки

нам надо убедится, что каждый символ из первой строки (внешний) цикл - встречается во второй строке (её мы будем полностью перебирать столько раз сколько символов в первой строке - так как перебор второй строки у нас вложенный)
столько же раз - сколько он встречается в первой - в противном случае - мы выходим из цикла - и выбрасываем сообщение о том, перестановку выполнить не возможно.

делается это как-то так:


int m = 0; // изначально на первый элемент
int n = 0; // для второй строки тоже
ine c1 = 1; // количество вхождений некоторого символа
// в первую строку (один символ 
//может встречать в строке несоколько раз)
 
int x = 1;// признак пригодности строк для перестановки
 // по-умолчанию  -пригодный (поднимаем флаг в единицу  -
/*  далее в цикле мы опустим его в ноль если 
какое-нибудь условие не выполнится*/

// поехали
while (str1[m] != 0) // условие перебора
{
	/*узнаём сколько раз очередной символ из первой строки встречается
	в этой же 
	самой первой строке  - для этого мы применяем собственную функцию - 
	она принимает два параметра  - первый- это символ типа char,
	а второй - это массив char-ов - то есть строка.
	*/
	c1 = how_many_symb_in_str(str1[m],str1);// эту функцию надо реализовать -
	/*то есть перебрать передаваемую строку сравнив каждый символ 
	с первыым переданным параметром - 
	и вернуть число совпадений*/
	
	n = 0;// обнуляем счётчик внутреннего цикла (чтобы каждый раз начинать сначала)
	int с2 = 0;// число вхождений некоторого символа во вторую строку
	while (str2[n] != 0)
	{
		
		if (str2[n] == str1[m]) с2++; // фиксируем, что встретили такой же символ
		n++;
	}
	/*сверяем число вхождений символа в первую и вторую строку*/
	if (c2 != c1) 
	{
       x = 0;// опускаем флаг - число символом одного типа не совпадает
	  break;//прерываем выолнение цилкла   - так как 
	  // дальнейшая проверка бессмысленна
	}
	
  m++; // переходим к следующему индексу
  // вращаем внешний цикл снова
}

/*прежде чем продолжать проверим результат работы цикла*/
if (x==1) 
{
// продолжаем работать
} else {} //выводим сообщение об ошибке. 

ПРИМЕЧАНИЕ:
факически блок

n = 0;// обнуляем счётчик внутреннего цикла (чтобы каждый раз начинать сначала)
	int с2 = 0;// число вхождений некоторого символа во вторую строку
	while (str2[n] != 0)
	{
		
		if (str2[n] == str1[m]) с2++; // фиксируем, что встретили такой же символ
		n++;
	}

- и есть реализация (одна из возможных) функции how_many_symb_in_str() - а потому - его можно заменить на вызов функции для второй строки.

Реализуйте эту часть задачи (пару раз проверив на тесте) - и пойдём дальше)

baton's picture

пара замечаний - из условия вытекает, что строки должны быть равны по длине, а так же кол-во символов, подлежащих перестановке должно быть равным в обоих строках.
ну че, буду думать.

vedro-compota's picture

да - верно - сначала прежде всего надо проверить на то, что длины строк равны - ща поправлю рассуждение выше.

_____________
матфак вгу и остальная классика =)

baton's picture

чтож, спасибо, постараюсь завтра разобраться.
один вопрос - функцию how_many_symb_in_str(str1[m],str1) "надо реализовать" - она отдельно описывается, я так понимаю?
о результатах отпишусь

vedro-compota's picture

да. она описывается отдельно (по структуре любая функция похожа на функцию main) + ещё надо будет вынести её описание.
очень полезно будет почитать это = http://fkn.ktu10.com/?q=node/3384

_____________
матфак вгу и остальная классика =)

baton's picture

не, я умею описывать функции - просто уточнил, что это неописанная функция нуждающаяся в описании))))))))))))))))))))
за ссылки спасибо - я там нового нашел немного - но сам ресурс весьма полезный.
для сравнения длин строк будет использована функция:

/* strlen example */ 
#include "stdio.h"
#include "conio.h"
#include "string.h" 
int main () { 
	char szInput[256]; 
	printf ( "Enter a sentence: " ); 
	gets (szInput); 
	printf ( "The sentence entered is %u characters long.\n" ,( unsigned )strlen(szInput)); 
	getch () ;
	return 0; 
} 
_____________________________________________
Источники(читать подробнее)=
Ключевые слова и фразы(для поиска)=http://www.cplusplus.com/reference/cstri...

конкретно функция будет представлять что-то вроде:

#include <stdio.h> 
#include "conio.h"
#include <string.h> 
#include <string>

int erere (int x) { 
	char szInput[256];
	printf ( "Enter a sentence: " ); 
	gets (szInput); 
	x = ( unsigned )strlen(szInput)); 
	getch () ;
	return x; 
} 
int main (int x){

 erere (x);
 printf ( "The sentence entered is %u characters long.\n" , x);
}

уточнение - вторая функция, выводящая х на экран, написана для иллюстрации. я заюзаю первую функцию два раза с разными переменными, потом сравню возвращаемые значения длин строк и дальше - прерывание или продолжение (если равны) программы

vedro-compota's picture

по-идее функция должна быть универсальна - то есть принимать два параметра - ничего на экран не выводить - это точно

_____________
матфак вгу и остальная классика =)

baton's picture

значит мое умение составлять функции на высоте...........

vedro-compota's picture

ваша функция работает? реализация уже фактически была приведена выше.

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

например функция может выглядеть так:

/* функция вернёт число вхождений символа simb -
(следует понимать ,что можно передать элемент массива 
- например str[m])*/
int how_many_symb_in_str(char simb,char* str)
{
	int n = 0;// просто счётчик
	int с2 = 0;// число вхождений некоторого символа simb в строку
	// изначально устанливаем в ноль
	while (str[n] != 0)
	{
		if (str2[n] == simb) с2++; // фиксируем, что встретили такой же символ
		n++; // накручиваем счётчик
	}
	return с2;// возвращаем число вхождений 
	//которое можно использовать далее "снаружи"
}

_____________
матфак вгу и остальная классика =)

baton's picture

слушай, как мы привязываем simb к другой строке?
туплю, но снизойдите....
по моему разумению это выглядит так:

int how_many_symb_in_str(char simb, char* str1, char* str2){    
    int n = 0, m = 1;// просто счётчики
    int с2 = 0; // число вхождений некоторого символа simb в строку
    // изначально устанливаем в ноль
    while (str2[n] != 0)
		simb = str1[m];
    {
        if (str2[n] == simb) {с2++; // фиксируем, что встретили такой же символ
        n++; // накручиваем счётчик
		}
		else 
			m++; // при неравенстве берем следующий символ строки1
    }
    return с2;// возвращаем число вхождений
    //которое можно использовать далее "снаружи"
}	                              

однако этот цикл может посчитать лишь вхождение только одного символа в строку1 игнорируя вероятность повторения этого символа в строке2

vedro-compota's picture

в смысле "привязываем" ?
если вы про вызов - то он же выше был написан - мы передаём элемент массива - каждый из элементов - типа char - =

c1 = how_many_symb_in_str(str1[m],str1);// str1[m] это и есть simb
// а str типа  - в строке выше это str1

кстати - в листиге выше - как уже было выше сказанно внутренний цикл не нужен - достаточно просто вызвать функцию и для второй строки -
типа внутри внешнего цикла просто поставить проверку =

if  ((how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2))
{
 //продолжаем цикл
} else {
// опускаем флаг - и вызываем break - чтобы зря не гнать цикл дальше 
//- так как одна буква уже некорректна
}

_____________
матфак вгу и остальная классика =)

baton's picture

ага
ну я и тупой на исходе дня
а тот цикл что я выше запилил - в мусорку?
короче, в мусорку

vedro-compota's picture

ммммм....для начала сформулируйте - что вообще делает функция которую вы написали.
та, что привел я - возвращает число вхождений символа в некоторую строку.

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

кстати -

while (str2[n] != 0)
        simb = str1[m]; // этол цикл
    { // а дальше уже не цикл
        if (str2[n] == simb) {с2++; // фиксируем, что встретили такой же символ
      // ПОЧЕМУ ПРОВЕРКА 2-ОЙ СТРОКИ КОГДА ИЩЕМ В ПЕРВОЙ?(судя по вашим словам)
        n++; // накручиваем счётчик
        }
        else
            m++; // при неравенстве берем следующий символ строки1
    }
    return с2;// возвращаем число вхождений
    //которое можно использовать далее "снаружи"

это лишь часть зверских причуд. но мне интересно почитать предлагаемый вами алгоритм - точнее описание того,что здесь написано)

_____________
матфак вгу и остальная классика =)

baton's picture

это был загон - когда шарики за ролики....
я решил, что предлагаемый вам код слишком сложен для моего самостоятельного написания - препод не поверит - и поэтому сделал последню попытку родить оригинальное извращение над строками.
данная функция проверяет наличие одинаковых символов в строках, уже проверенных на равенство длинны:

int checkArray(char *str1, char *str2){	// проверка наличия одинаковых символов
	int n = 0, m = 0, x;	

		while((str1[n] != 0) || (str2[m] != 0)){         // проверка наличия одинаковых символов
				 m = 0; // счетчик каждый раз обнуляется - счет с нулевого члена
			if(str1[n] == str2[m]){		//если Nный символ строки1 = Mному ->
                                                     // -> символу строки2, то m+1 ->
				m++;  // -> берется (m+1)ный символ стр1 на случай повтора символа
				if(str2[m] = 0) // а рано или поздно он будет = 0. 
					n++; // тогда берется следующий член строки1
			
				else
				m++;  // иначе берется следующий член строки2
			}
			if ((str2[m] = 0) && (str1[n] != str2[m])){   // если один из символов строки1 неравен -
                                                     //  -  ни одному символу строки2, х=0, выпад из цикла
				x = 0;
				break;
			}
		else
			x = 1;		// иначе х = 1, цикл продолжается до выполнения своего условия
		}

	return x;
}

уже запиливая комментарий я осознал, что цикл не подсчитывает количество вхождений одинаковых символов и не проверяет равенство этих вхождений в строках...
придется все же сдать эти зверства в кунсткамеру.....

vedro-compota's picture

моя функция - это довольно тривиальное решение, рассчитанное на сравнение строк не очень большой длинны.
если бы строки были по пару миллионов символов - то имело бы смысл - создавать массив уже проверенных символов -чтобы не запускать каждый раз подсчёт числа вхождений для каждого символа - в случае если обе строки уже были проверены для точно такого же символа ранее.

так что моя функция вполне себе обычна

_____________
матфак вгу и остальная классика =)

baton's picture

тривиальное для курса на котором вы учитесь (а возможно уже отучились), но не для дибила-первака-меня ((((((((((((((((((((((((((((((((((
хотя я, в принципе, понял вашу функцию.
юзаю в неизменном виде - какой же я тупой.......

поясните еще - str2 не заявлена в аргументах функции - поэтому меня беспокоит строка:

if (str2[n] == simb) с2++; // фиксируем, что встретили такой же символ
vedro-compota's picture

это опечатка .
следует исправить на =

if (str[n] == simb) с2++;

_____________
матфак вгу и остальная классика =)

baton's picture

int how_many_symb_in_str(char simb,char* str)  // наша полюбившеяся функция
{
    int n = 0;// просто счётчик
    int с2 = 0;// число вхождений некоторого символа simb в строку
				 // изначально устанливаем в ноль
    while (str[n] != 0)
    {
        if (str[n] == simb) с2++; // повторение
        n++; // следующий член
    }
    return с2;     //число вхождений
    
}
             
int checkArray(char *str1, char *str2){	// проверка наличия одинаковых символов (после проверки длинны строк)
	int n = 0, m = 0, x, s1, s2, t;	
		while((str1[n] != 0) || (str2[m] != 0)){ // цикл по проверке наличия одинаковых символов // условие перебора

    /*
	узнаём сколько раз очередной символ из первой строки встречается
    в этой же первой строке -  применяем  функцию how_many_symb_in_str(символ char,массив char)
    */
    s1 = how_many_symb_in_str(str1[m],str1); 
			  t = 0;// обнуление счётчикa внутреннего цикла
		int с2 = 0;// число вхождений символа во вторую строку
		   while (str2[t] != 0){
			   	s2 = how_many_symb_in_str(str1[m],str2);
				if (str2[t] == str1[m]) {
					с2++;                           // фиксируем обнаружение такого  же символа
					x=1;
				}
					 t++; // берется следующий член строки2
					 if (с2 != s1) {   //сверяется число вхождений символа в первую и вторую строку
						 x = 0;
						 break;     // выпадение
					 }
					 m++; // берется следующий член строки1
				if (x!=1) {     // проверка условия равенства совпадений в строках
				    break;            //выпад 
					printf("невозможно выполнить перестановку - есть разные символы"); //сообщение об ошибке. 
				}
		   }
		}
		return x;
}
vedro-compota's picture

int checkArray(char *str1, char *str2){ // проверка наличия одинаковых символов (после проверки длинны строк)

зачем это?..........
функция которая считает число вхождений уже даёт нам инфу о наличии символа или его отсутствии =

int x = 1;// флаг по-умолчанию поднят
// сначала проверим что длины строк равны =
if (strlen(str1) == strlen(str2))
{
	while (str1[m] != 0)
	{ // проверям
		if  ((how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2))
			m++;
		   else 
		   {
			   x = 0;
			   break; // выхожим из цикла
		   }
	}
} else x = 0; // опять же - опускаем флаг 
/*
ПОЯСНЕНИЕ:
если строки одинаковой длинны - т.е -
(strlen(str1) == strlen(str2))
и при этом каждый символ встречает во второй строке
 столько же раз сколько в первое  - т.е = 
 (how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2))
 ТО  -значит ПЕРЕСТАНОВКУ ВЫПОЛНИТЬ МОЖНО
*/

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

как отдельная функция =

checkArray(char *str1, char *str2)
{
    int m = 0;
	int x = 1;// флаг по-умолчанию поднят
	// сначала проверим что длины строк равны =
	if (strlen(str1) == strlen(str2))
	{
		while (str1[m] != 0)
		{ // проверям
			if  ((how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2))
				m++;
			   else
			   {
				   x = 0;
				   break; // выхожим из цикла
			   }
		}
	} else x = 0; // опять же - опускаем флаг 
	return x; // Я ТОЖЕ ВОЗВРАЩАЮ X ))))))))
}

_____________
матфак вгу и остальная классика =)

baton's picture

протупив около.. не знаю, сколько времени я тупил над готовым по сути кодом - благословясь приступаем к перестановке символов.
там я тоже собираюсь тупануть - т.к. это может занять много места, создаю следующую тему - http://fkn.ktu10.com/?q=node/3397