Анаграммы на Android

Как-то застал жену за придумыванием всех слов , которые можно составить из букв слова «лекарство» ( flash-игра такая), немного помог ей в этом.  Мысль об автоматизации возникла сразу, смысл игры при этом, конечно, теряется, но стало интересно  - насколько много слов можно составить и насколько быстро такой поиск будет выполняться на смартфоне.

Для начала нашел словарик (в текстовом формате) из  47612 существительных в единственном числе, именительном падеже . Словарь конечно  попался кривоватый – многих слов нет, зато есть, например, слово «та» (то ли русское местоимение, то ли буква арабского алфавита, то ли знак каны). Этот словарик будем загружать в массив строк при старте программы.

Для введенного слова посчитаем количество для каждой из букв. Для каждой буквы словарного слова тоже будем считать количество и, если для всех букв словарного слова это количество будет меньше или равно аналогичному  значению для введенного слова, то словарное слово нам подходит.  Частным случаем тут будет поиск анаграмм – когда найденное словарное слово имеет ту же длину,  что и исходное. Возможно, существует и более производительный алгоритм, но реализовал то, что сразу пришло в голову.

В итоге для слова «лекарство» за 3 секунды на HTC Desire было найдено 175 вариантов.

Ниже исходник получившейся программы.

/**

 * Anagram Builder

 * Copyright (C) 2012 Anmyst

 * @author Anmyst

 * @version 1.0

*/

package com.anmyst.anagramru;

import java.io.BufferedReader;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.HashMap;

import android.app.Activity;

import android.os.Bundle;

import android.os.Environment;

import android.view.View;

import android.view.View.OnClickListener;

import android.widget.ArrayAdapter;

import android.widget.Button;

import android.widget.CheckBox;

import android.widget.EditText;

import android.widget.ListView;

import android.widget.Toast;

/**

 * Anagram Builder activity

 */

public class AnagramruActivity extends Activity {

 private ArrayList <String> arr; //словарь

 private ArrayAdapter <String> adapt; //список результатов

 private HashMap map; // хранит количество букв для каждой буквы в слове

 /**

  * Запуск поиска анаграмм

  */

 private OnClickListener ButtonStart_click = new View.OnClickListener(){

 

  @Override

  public void onClick(View v) {

   final EditText eWord = (EditText)findViewById(R.id.editTextWord);

   String sWord = eWord.getText().toString();

   if (sWord.equalsIgnoreCase(""))

    return;

  

   String sDict;

   adapt.clear();

   map.clear();

  

   for(int i = 0; i < sWord.length(); i++){

    map.put(sWord.charAt(i), CharCount(sWord,sWord.charAt(i)));

   }

  

   boolean anagram = false;

   final CheckBox chkAnagram = (CheckBox)findViewById(R.id.checkBoxAnagram);

   if (chkAnagram.isChecked())

    anagram = true;

  

   int key;

   int ok;

   int counter = 0;

   for(int j = 0; j < arr.size(); j++){

    sDict = arr.get(j);

    ok = 1;

    for (int k = 0; k < sDict.length(); k++){

    

     if(map.containsKey(sDict.charAt(k)))

      key = (Integer)map.get(sDict.charAt(k));

     else

      key = 0;

     if (CharCount(sDict, sDict.charAt(k)) > key){

      ok = 0;

      continue;

     }

    }

    if (ok == 1){

     if ((!anagram) || (sDict.length() == sWord.length())){     

       adapt.add(sDict);

       counter++;     

     }     

    }

    

   }

   showToast("Found:" + counter);

  

  }

 };

 /**

  * Вывод короткого сообщения

  * @param s Строка сообщения

  */

 private void showToast(String s){ 

  Toast mess = Toast.makeText(getApplicationContext(), s, Toast.LENGTH_SHORT);

  mess.show(); 

 }

 /**

  * Считает количество заданных символов в строке

  * @param s исходное слово

  * @param c символ для которого расчитывается количество

  * @return количество заданных символов в слове

  */

 private int CharCount(String s, char c){

  int cnt = 0;

  for (int i = 0; i < s.length(); i++){

   if (s.charAt(i) == c)

    cnt++;

  }

  return cnt;

 }

 /**

  * Чтение строк из файла словаря

  * в массив arr

  * @param fname имя файла

  */

 private int ReadFile(String fname)

 {

  String s1;

  try{

   File f = new File(Environment.getExternalStorageDirectory() + "/DictRu/" + fname);

   FileInputStream fileIS = new FileInputStream(f);

   BufferedReader buf = new BufferedReader(new InputStreamReader(fileIS, "windows-1251"));

   String readString = new String();

   while((readString = buf.readLine()) != null){

    s1 = readString.toLowerCase();

    arr.add(s1);

   }

  } catch (FileNotFoundException e) {

      e.printStackTrace();

      return 1;

   } catch (IOException e){

    e.printStackTrace();

      return 2;

   }

  return 0;

 }

 /**

  * Загрузить словарь из файла

  */

 private void LoadDictionary(){

  arr.clear();

  if (ReadFile("dictru.txt") != 0){

   showToast("Load Dictionary Error!");

  }

  else{

   showToast("Dictionary loaded!");

  }

  return;

 }

/** Called when the activity is first created. */

@Override

public void onCreate(Bundle savedInstanceState) {

    super.onCreate(savedInstanceState);

    setContentView(R.layout.main);

   

    final Button bStart = (Button)findViewById(R.id.buttonStart);

    bStart.setOnClickListener(ButtonStart_click);

   

    map = new HashMap();

   

    arr = new ArrayList <String>();

    adapt = new ArrayAdapter<String> (this,android.R.layout.simple_list_item_1,android.R.id.text1);

    adapt.setNotifyOnChange(true);

   

    ListView list = (ListView)this.findViewById(R.id.listViewResults);

    list.setAdapter(adapt);

   

    LoadDictionary();

}

}