Рекурсивный перебор. Вылет за границы массива

@serguk071 · Регистрация: 17.05.2012

Author24 — интернет-сервис помощи студентам

ка, состоящая из попарно различных символов (буквы латинского алфавита и цифры). Требуется вывести все перестановки символов данной строки в алфавитном порядке.
Ввод:
AB
Вывод:
AB
BA
Ввод:
IOX
Вывод:
IOX
IXO
OIX
OXI
XIO
XOI

Написал код, вроде должно работать. Но если по алгоритму, то вылетает за границы массива. А если в цикле сделать на одну итерацию меньше то выводит не то, что нужно.

Вылет за границы в 33 строке в общем коде.
Вот кусочек, в котором вылетает, ниже полный код.

C#

listBox1.Items.Clear();
            s = richTextBox1.Text.ToString();
            n = s.Length;
            for(int i=0; i<n-1; i++)
                for(int j=0; j<n-i; j++)
                    if(s[j]>s[j+1])
                    {
                        char[] arr = s.ToCharArray();
                        ch = arr[j];
                        arr[j] = arr[j+1];
                        arr[j + 1] = ch;
                        s = new string(arr);
                    }
 
Полный код:

C#

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
 
        private string s;
        bool[] used = new bool[10];
        int[] a = new int[10];
        int n;
        char ch;
 
        private void button1_Click(object sender, EventArgs e)
        {
            listBox1.Items.Clear();
            s = richTextBox1.Text.ToString();
            n = s.Length;
            for(int i=0; i<n-1; i++)
                for(int j=0; j<n-i; j++)
                    if(s[j]>s[j+1])
                    {
                        char[] arr = s.ToCharArray();
                        ch = arr[j];
                        arr[j] = arr[j+1];
                        arr[j + 1] = ch;
                        s = new string(arr);
                    }
            for (int i = 0; i < n; i++)
                used[i] = true;
            dfs(1);
        }
 
        public void dfs(long v)
        {
            char[] arr= new char[n];
            if (v == (n + 1))
            {
                for (int i = 0; i < n; i++)
                {
                    arr[i] = s[a[i]];
                }
                string ps = new string(arr);
                listBox1.Items.Add(ps);
            }
            for(int i=0; i<n; i++)
                if(used[i])
                {
                    a[v] = i;
                    used[i] = false;
                    dfs(v+1);
                    used[i] = true;
                }
        }
    }
}

Помогите пожалуйста, не могу найти, где вылетает.

@~~AIMaster~~ · 11.04.2013, 18:13

C#

1	for(int j=0; j<n-i-1; j++)

@da1z · 11.04.2013, 18:13

Вместо

Сообщение от serguk071

for(int j=0; j<n-i; j++)

надо

C#

1	for(int j=0; j<n-i-1; j++)

Т.к. когда i=0 , j будет = n, что есть s.length и тут получается выход за пределы массива

@serguk071 · 11.04.2013, 18:31 **[ТС]**

Сообщение от da1z

Вместо
надо

C#

1	for(int j=0; j<n-i-1; j++)

Т.к. когда i=0 , j будет = n, что есть s.length и тут получается выход за пределы массива

Пробовал. Я же написал выше, что тогда выводит неправильный ответ. А код такой же один в один на фри паскале работает идеально.

Добавлено через 1 минуту

Сообщение от serguk071

Если в цикле сделать на одну итерацию меньше то выводит не то, что нужно.

Сейчас скину прокомментированный код, чтобы легче читать было.

C#

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
 
        private string s; // строка символов
        bool[] used = new bool[10]; // метка того, использовали ли мы элемент под номером i в перестановке
        int[] a = new int[10]; // текущая перестановка
        int n;  // n - длина строки
        char ch;
 
        private void button1_Click(object sender, EventArgs e)
        {
            listBox1.Items.Clear();
            s = richTextBox1.Text.ToString();
            n = s.Length; // длина строки
            for(int i=0; i<n-1; i++)
                for (int j = 0; j < n - i; j++)
                    if (s[j] > s[j + 1]) // это сортировка символов строки, потому что перестановки генерируются в алфавитном порядке
                    {
                        char[] arr = s.ToCharArray();
                        ch = arr[j];
                        arr[j] = arr[j+1];
                        arr[j + 1] = ch;
                        s = new string(arr);
                    }
            for (int i = 0; i < n; i++)
                used[i] = true; // обнуление
            dfs(1); // запуск рекурсии
        }
 
        public void dfs(long v) // процедура генерации
        {
            char[] arr= new char[n];
            if (v == n + 1) // если перестановка сгенерирована
            {
                for (int i = 0; i < n; i++)
                {
                    arr[i] = s[a[i]]; // то выводим ее посимвольно
                }
                string ps = new string(arr);
                listBox1.Items.Add(ps);
            }
            for (int i = 0; i < n; i++) // иначе ищем элемент, который мы поставим на v-ое место
                if (used[i]) // если элемент не использован
                {
                    a[v] = i; // то ставим его на v-ое место
                    used[i] = false; // метим, что это элемент мы брали
                    dfs(v + 1); // переходим на следующую позицию
                    used[i] = true; // откат обратно
                }
        }
    }
}

Добавлено через 4 минуты
А вот тот же код на паскале:

Pascal

var s:string; // строка символов
    used:array[0..10] of boolean; // метка того, использовали ли мы элемент под номером i в перестановке
    a:array[0..10] of longint; // текущая перестановка
    i,n,j:longint; // n - длина строки, i,j - счетчики
    ch:char;
 
procedure dfs(v:longint); // процедура генерации
var i:longint; // счетчик
begin 
 if (v=n+1) // если перестановка сгенерирована
  then
   begin
    for i:= 1 to n do
     write(s[a[i]]);  // то выводим ее посимвольно
     writeln;
    exit;
   end;
  for i:= 1 to n do // иначе ищем элемент, который мы поставим на v-ое место
   if used[i] then // если элемент не использован
    begin
     a[v]:=i; // то ставим его на v-ое место
     used[i]:=false; // метим, что это элемент мы брали
     dfs(v+1); // переходим на следующую позицию
     used[i]:=true; // откат обратно
    end;
end;
 
 
begin
 readln(s); // ввод строки
 n:=length(s); // длина строки
 for i:= 1 to n-1 do  
  for j:= 1 to n-i do
   if (s[j]>s[j+1]) // это сортировка символов строки, потому что перестановки генерируются в алфавитном порядке
     then
      begin
       ch:=s[j];
       s[j]:=s[j+1];
       s[j+1]:=ch;
      end;
 for i:= 1 to n do
  used[i]:=true; // обнуление
 dfs(1); // запуск рекурсии
end.

Добавлено через 1 минуту

Сообщение от AIMaster

C#

1	for(int j=0; j<n-i-1; j++)

Пробовал. Я же написал выше, что тогда работает, но выводит неправильный ответ. А код такой же один в один на фри паскале работает идеально.

Может я криворуко переписал. Тогда простите

Ниже код есть, сравните если не сложно.

Спасибо за помощь и попытки помощи огромное!)

@da1z · 11.04.2013, 18:45

Сообщение от serguk071

Пробовал. Я же написал выше, что тогда работает, но выводит неправильный ответ.

Тогда ищите ошибку в алгоритме

@serguk071 · 11.04.2013, 18:47 **[ТС]**

Сообщение от da1z

Тогда ищите ошибку в алгоритме

Но почему на паскале то работает?)))))
Вот в чем самый большой вопрос

@da1z · 11.04.2013, 18:48

дел

@serguk071 · 11.04.2013, 18:50 **[ТС]**

Сообщение от da1z

дел

Что простите?)

@da1z · 11.04.2013, 18:54

Покажите, что выводит(Не правильный вариант)

@serguk071 · 11.04.2013, 19:02 **[ТС]**

Сообщение от da1z

Покажите, что выводит(Не правильный вариант)

Прикрепил вывод в трех случаях

@da1z · 11.04.2013, 19:16

C#

1	dfs(1); // запуск рекурсии

Мне кажется тут с нулём надо вызвать

@serguk071 · 11.04.2013, 19:27 **[ТС]**

Сообщение от da1z

C#

1	dfs(1); // запуск рекурсии

Мне кажется тут с нулём надо вызвать

Ничего не выводит совсем.

У меня уже просто аж интерес, где же ошибка...

@da1z 192 / 192 / 29 Регистрация: 03.12.2009 Сообщений: 853
	11.04.2013, 18:45	5
	Сообщение от serguk071 Пробовал. Я же написал выше, что тогда работает, но выводит неправильный ответ. Тогда ищите ошибку в алгоритме 1

@serguk071 2 / 2 / 0 Регистрация: 17.05.2012 Сообщений: 13
	11.04.2013, 18:47 [ТС]	6
	Сообщение от da1z Тогда ищите ошибку в алгоритме Но почему на паскале то работает?))))) Вот в чем самый большой вопрос 0

@da1z 192 / 192 / 29 Регистрация: 03.12.2009 Сообщений: 853
	11.04.2013, 18:48	7
	дел 1

@serguk071 2 / 2 / 0 Регистрация: 17.05.2012 Сообщений: 13
	11.04.2013, 18:50 [ТС]	8
	Сообщение от da1z дел Что простите?) 0

@da1z 192 / 192 / 29 Регистрация: 03.12.2009 Сообщений: 853
	11.04.2013, 18:54	9
	Покажите, что выводит(Не правильный вариант) 1

@serguk071 2 / 2 / 0 Регистрация: 17.05.2012 Сообщений: 13
	11.04.2013, 19:02 [ТС]	10
	Сообщение от da1z Покажите, что выводит(Не правильный вариант) Прикрепил вывод в трех случаях Миниатюры 0